Efektivita algoritmů

Obdržel jsem hlášení, že na Mars bude vyslána nová průzkumná sonda a my jsme odpovědní za jedinou věc - což je naprogramování algoritmu pro sondu, který zjišťuje, jestli je číslo prvočíslem. Řekněme třeba, že naše sonda komunikuje pomocí RSA. Uvnitř potřebuje algoritmus, který dokáže vykonávat test prvočíselnosti. Když navrhujete průzkumnou sondu, nebo cokoliv, co bude putovat do vesmíru, musíte byt hodně efektivní ve všech směrech. Součástky musí být velice lehké, a množství energie spotřebováno subsytémy musí být minimální. Musíte šetřit energií a hmotou v každém kroce procesu designu. Naší prací je, že musíme být schopní pracovat s čísly takovýchto velikostí... ...a vše se musí dít velmi rychle. Když navolíme hodně malé číslo, řekněme pouze 90, musí to být program schopen zvládnout téměř tak rychle jako celé tohle číslo. Když vstupní číslo roste, nechceme pozorovat žádné viditelné zpomalení. Teď budu chtít analyzovat dotazy uživatelů, nebo nápady, které uživatele měli, které byly velice dobré. Z matematického hlediska. Zjišťujeme jestli je 'n' prvočíslo nebo složené číslo. Jestli máme nějaké číslo 'n', myslete na prostor se všemi možnými čísly n. Když n je kupříkladu 100, pak tenhle prostor bude od 2 do 100. A náš algoritmus prohledává tento prostor. Pod algoritmem můžete rozumět prohledávání prostoru, kde se v každém kroku ptá - berte to jako krok- primitivní krok, který pokládá otázku. Otázka je v podstatě testem, zda se jedná o složené číslo. Jsme u čísla 'a', a jednoduchou metodou dělitelnosti zjišťujeme jestli je n dělitelné číslem a. Zkusíme to, zkusíme jestli zbytek po dělení bude 0. Pokud ano, znamená to, že 'a' je dělitelem čísla 'n'. Pak můžeme říct: "Jsme si naprosto jistí, že se jedná o složené číslo." Jinak si kroky nejsme jistí, jelikož se může jednat o prvočísla, takže prohledáváme až do konce. Pamatujte, že naše zeď byla odmocnina čísla 'n'. Nejhorší situace nastane pokud je 'n' prvočíslem, protože pak budeme prohledávat až do odmocniny z 'n'. A pak můžeme říct, Jedná se o prvočíslo! A jsme si tím naprosto jistí. Jestli je n násobkem dvou prvočísel, třeba číslo 7 vezmeme si 7 krát 7 7 krát 7 bude 49. Když budeme zkoušet náš algoritmus na čísle 49, nastane nejhorší případ, a to že budeme muset počítat až do odmocniny z n. První sada otázek, Např. TheFourthDimension se ptal: "Pokud už vyřadíme 2 jako nedělitelné, všechny násobky čísla 2 mohou být vyřazeny. To samé se týče čísla 3 To samé se týče čísla 3, 4 To samé se týče čísla 3, 4, 5 To samé se týče čísla 3, 4, 5, etc. Tohle je skvělý postřeh. Náš původný algoritmus postupoval krok za krokem, ale my bychom mohli používat schémata pro složená čísla, které známe. Například víme, že pokud je číslo dělitelné 2, určitě se jedná o složené číslo. Pokud je větší než 2, jelikož 2 je prvočíslo. Pak můžeme říct, 4 je složené číslo... Zapomněl jsem na 5, promiňte. 4 4, 6 4, 6, 8 4, 6, 8, 10 ... Nebo místo toho můžeme vzít jiný krok: 3 3, 5 3, 5, 7 3, 5, 7, 9 ... Takže tyhle typy dotazů se všechny snaží zmenšit prostor. Když vyřadíme všechna sudá čísla, prohledávaný prostor se změní z původné odmocniny z 'n' na odmocninu z 'n' děleno 2. Můžeme najít také další schémata pro složená čísla abychom mohli tento prostor ještě zmenšit. Jiný typ dotazů se týče hledání svědků složeného čísla, to znamená, že hledáme 'a', které nám umožňí tvrdit, že 'n' je složené číslo. Lola napsala: "Nepomohlo by na zredukování času zanechání konstrukce 'loop' když 'primeCheck == false' ? Ano, ovšemže je to správně a je to něco, co chceme udělat. Když hledáme pomocí nějakého kroku, který je definován používaným schématem, a nalezneme svědka složeného čísla, znamená to, že prošel naším testem a my můžeme s jistotou říct, že se jedná o složené číslo. Brzy bychom se měli zastavit. Řekneme si, "Jsme u konce." Nebudeme pokračovat s hledáním. Tohle skoré zastavení je skvělé, ale nepomáhá nám v nejhorším případě, tedy pokud 'n' je pročíslo, skoré zastavení nám nepomůže. Teď si můžeme představit, jak nám tato vylepšení pomohou zmenšit prostor a tím zabránit mnoha kontrolám, které musí počítač udělat (a záleží na našem počítači) a snížit čas, který je potřeba. Teď vám mohu ukázat příklad, co jsem připravil, který nám pomáhá porovnat kolik kroků programy potřebovaly na dva různé algoritmy. Nalevo je Algoritmus A, založen na zkušebním dělení, který kontroluje od 2 do odmocniny z 'n'. Napravo máme Algoritmus B, kterému budeme říkat "vylepšený algoritmus". V tomto případě jsem aplikoval kontrolu zda se jedná o číslo dělitelné 2, takže děláme pouze polovinu všech kroků, a rovněž se Algoritmus B ukončí dřív. Není to dokonalé, přidal jsem pár uživatelských úprav, takže můžeme vidět co se děje a budu si s tím hrát, abych vám to lépe ukázal. Když to zde posunu, vidíme Algoritmus A. Máme výstup, zda se jedná o složené číslo nebo o prvočíslo, a dole vidíte počet vykonaných kroků. První věc, které je třeba si všimnout, je na pravé straně. Každému druhému číslu je potřeba pouze jeden krok, a víme proč tomu tak je - když se jedná o sudé číslo, jako je tohle, program skončí. Našemu původnímu algoritmu to trvalo 314 kroků, zatímco náš nový algoritmus to zvládl za jediný krok, protože zjišťoval, jestli jde o číslo dělitelné 2. Tohle vypadá jako velice pěkné vylepšení. Nicméně, když zvětšujeme naší vstupní hodnotu, všimněte si jak se navyšuje počet kroků, sloupec narůstá a zbarví se dočervena když se přibližujeme ke kraji, kde narazíme. Tahle červená linie nahoře je limit kroků. Když se sloupec dostane až sem, selhali jsme, to znamená, že naše průzkumná sonda se rozbije, v tomhle případě spadne prohlížeč, takže se k ní pokusím dostat blíž. Teď jsem u ní hodně blízko a jde to hrozně pomalu, cítím, že mi co nevidět spadne prohlížeč a vyhodí to kruh smrti. Všimněte si, že našemu vylepšenému algoritmu to trvalo pouze 2 kroky, ale myslete na ten horší případ. Mám zde několik velkých prvočísel na vyzkoušení. Musíme zvládnout jakýkoliv případ, jelikož nevíme, co budeme házet do našeho algoritmu. Když do něj hodím velké prvočíslo, podívejte co to udělá: Jak víme, Algoritmu B to trvá polovinu všech kroků v nejhorším možném případě, ale zde to pořád chce hodně kroků. Protože jde o nejhorší případ, že ano? Teď se blížíme k pádu, a tohle není zas tak velké prvočíslo. Jsme pořád hodně pod 15 cifer. A když do našeho algoritmu zadám 12-ciferné číslo podívejme se, co to udělá: Došlo k prodlevě, možná se program zhroutí... Podívejte, co se stalo: oba dva algoritmy jsou příliš nad limitem, takže to nefungovalo. Náš vylepšený algoritmus ještě není dost dobrý. Teď ale víme, co se snažíme vylepšit. Jde o "počet kroků v nejhorším možném případě". Taky zde máme tuto skvělou pomůcku, která nám umožňuje pozorovat jak rychle to narůstá - jak rychle počet kroků narůstá s velikostí vstupní hodnoty. Dole vysvětluji jak jsem to vytvořil, takže si můžete vytvořit vlastní algoritmus, porovnat ho se základním a vidět o kolik lépe to umíte udělat vy.