?
Trocha algoritmizace
Ve škole máme jako jeden z předmětů také algoritmizaci, a tak mě napadlo podělit se s vámi o část svých nabytých znalostí.
Začal bych starou programátorskou pravdou: Napsat algoritmus, který bude řešit nějaký problém (např. počítat Fibonacciho posloupnost), je jednoduché, ale napsat ho kvalitně (aby byl co možná nejrychlejší), je umění.
Rychlost algoritmů se vyjadřuje většinou pomocí asymptotické složitosti algoritmů. Vytvoříme si vlastně matematický model našeho algoritmu, tedy nakreslíme si graf, kde na osu x vynášíme množství vstupních dat a na osu y počet průchodů cyklem (operací prováděných v algoritmu). Nyní musíme porovnat náš výsledek se známými elementárními funkcemi a vybrat tu, která roste srovnatelně rychle nebo rychleji než naše funkce. Pokud tedy naše funkce lze popsat funkcí x^2 - 2x + 1. V úvahu nyní bereme jen ty části funkce, které nejvíce "rostou". 2x a 1 tedy odškrtneme a vyjde nám, že elementární funkce, která roste srovnatelně rychle je x^2. To nyní zapíšeme jako O(n^2) [čti ómikron].
Složitosti
| O(log(n)) |
|---|
| O(n) |
| O(n*log(n)) |
| O(n^2) |
| O(n^3)... |
| O(a^n)... |
| O(n!) |
Nyní se podívejme na hezký příklad. Vezměme si Fibonacciho posloupnost.
Fib(n) = Fib(n-1) + Fib(n-2);
Jak je vidět jedná se o rekurzivní funkci se dvěmi větvemi, a proto má složitost O(n^2). Jednoduchý zápis této funkce:
function Fib(x){
return (x<2)? x : Fib(n-1) + Fib(n-2);
}
Zkusme se ale zamyslet a podívat se jak tento algoritmus pracuje. Nepočítá náhodou výsledek fib funkce několikrát pro ty samé hodnoty? A zcela zbytečně? Zkusíme tedy vytvořit statické pole, do kterého budeme ukládat jednotlivé mezivýsledky a schválně, co to udělá.
function fib($x){
if($x<2){
return $x;
} else {
if(!$pole_fib[$x-2]){
$pole_fib[$x-2] = fib($x-2);
}
if(!$pole_fib[$x-1]){
$pole_fib[$x-1] = fib($x-1);
}
return $pole_fib[$x-1] + $pole_fib[$x-2];
}
}
Pokud vložíte do funkce nějaký inkriminant (k++), zjistíte, že se tato funkce zavolá při svém výpočtu pouze n+1 krát. To je krásné. Podařilo se nám funkci optimalizovat ze složitosti O(n^2) na pouhou O(n).
Z toho tedy vyplývá, že bysme při psaní algoritmů, na jejichž rychlosti nám záleží, neměli spěchat a snažit se nejdříve celou situaci zachytit na papír. Po napsání algoritmu zjistíme jeho složitost a zkusíme zapřemýšlet, zda by to nešlo i nějak jednodušeji...
Hodnocení
Komentáře
2006-12-20 11:04:00
2008-04-26 13:14:23
chci se naucit programovat ale moje znalosti matematiky odpovidaji 4 stupni gymnazia cili 9 tride tak nevim nevim jestli do toho proniknu jak tak na to koukam....
[imp][/imp]