Předběhne můj program zajíce?

Nebo alespoň želvu?

Mami, potřebuju rychlejší počítač!

Bude tvůj program stíhat limit, když ho pustíš na lepším počítači? Jak vlastně určujeme rychlost programů? A můžeš znát rychlost algoritmu, když jsi ho ještě nenaprogramoval a nemůžeš ji změřit?

Předně ti musíme prozradit, že rychlost programu neurčujeme podle toho, jak rychle program seběhne na konkrétním počítači. Je to proto, že různé počítače jsou různě rychlé. Další věcí je, že rychlost programu záleží na jeho vstupních datech. Pro některé vstupy může program odpovědět hned (třeba na to, že dvojka je prvočíslo), některé mu dají zabrat víc.


Proč? Stačí zrychlit na O(n)

Budeme tedy určovat rychlost programů a algoritmů podle toho, kolik jednoduchých operací musí počítač provést, aby vydal výsledek, a už nezáleží na tom, jestli ta jednoduchá operace bude sčítání, odčítání, násobení, přiřazení hodnoty do proměnné, vytvoření proměnné, čtení jednoho znaku ze vstupu a podobně, všechny tyto operace trvají víceméně stejný zlomek sekundy. A to všechno určujeme v nejhorším případě (na tom vstupu, na kterém bude program nejpomalejší, protože i na ten musí být program připraven) a vzhledem k velikosti čísla na vstupu.

Různé počítače a také programovací jazyky se mezi sebou liší, stejné jednoduché operace můžou dělat trochu jinak a také trochu jinak rychle. Nebudeme tedy určovat přesné číslo, ale jenom přibližný odhad. Na to si zavedeme značení O(x), kde x je výraz, ve kterém většinou figuruje délka vstupu. O(x) je takzvaný asymptotický odhad, tedy nás ve výrazu x zajímá hlavně člen, který roste nejrychleji. Ten nás totiž zdržuje nejvíc. Také nás nezajímá konstanta před ním, protože 3n roste hodně podobně rychle jako n i jako 15n.

Například pokud máme program, který udělá 4n³ + 120n² + 200n + 1 operací, kde n je délka vstupu, tak řekneme, že program běží v O(n³), jelikož roste nejrychleji. Zkuste si dosadit do výrazu za n hodně velké číslo, třeba milion, potom bude řádově větší než ostatní členy. Také nás nezajímá, že je to celé 4krát, protože to je jenom konstanta. Ta se dá navíc těžko spočítat naprosto přesně.


Příklad

Dost teorie, zkusíme si určit složitost několika algoritmů řešících stejnou úlohu. Na vstupu dostanete posloupnost čísel délky n, najděte v ní souvislý úsek s co největším součtem. První řešení (hloupé): Vyzkoušíme všechny dvojice čísel, sečteme všechny členy mezi nimi a ze všech pokusů vybereme ten nejlepší.

Pseudokód:
// i-tý prvek máme uložen jako p[i], aktuální maximum je uloženo v akt_max.
Pro i od 1 do n:
     Pro j od i do n:
         soucet = 0
         Pro k od i do j:
              soucet = soucet + p[k]
         Pokud akt_max < soucet:
              akt_max = soucet

Jak je program rychlý? Vybere všechny dvojice, těch je zhruba , jelikož pro každý vybraný prvek může vybrat až n jiných. Mezi každou dvojicí však potřebujeme spočítat součet, tedy pro každou dvojici až n sčítání, tedy náš program běží v čase O(n³).

Druhé řešení (lepší): Co kdybychom si pamatovali pro každý index i součet čísel až po tento index? (Tomu říkáme prefixový součet, prefix je něco jako předpona, všechna čísla od začátku až před i.) Potom bychom mohli součet mezi prvky i a j zjišťovat rychleji. Jenom bychom od prefixového součtu j odečetli součet prvků před i.

//p[i] i-tý prvek posloupnosti, pref[i] - prefixový součet od i.
Pro i od 1 do n:
    Když i == 1: 
        pref[i] = p[i]
    jinak:
        pref[i] = pref[i-1]+p[i]
Pro i od 1 do n:
    Pro j od i do n:
        Když akt_max < pref[j] - pref[i]:
            akt_max = pref[j] - pref[i]

Tím jsme si pomohli. Sice na začátku musíme předpočítat prefixové součty, ale potom je třeba vyzkoušet jen všechny dvojice. Tedy uděláme n + n² operací (n za spočítání prefixových součtů), ale n je zanedbatelné, tedy složitost je O(n²).

Poslední řešení (nejlepší): Hlavní myšlenkou pro toto řešení je, kde může největší úsek začínat a končit. Určitě musí být pravda, že pokud máme před nebo za maximální posloupností nějákou souvislou podposloupnost, která má kladný součet, potom naši maximální můžeme rozšířit o tuto podposloupnost. Tedy naši podposloupnost neustále rozšiřujeme doprava, pokud součet klesne pod nulu, vše zahodíme a začínáme od nuly.

// p[i] i-tý prvek posloupnosti
Pro i od 1 do n:
    soucet = soucet + p[i]
    Pokud akt_max < soucet: 
        akt_max = soucet
    Pokud soucet < 0:
        soucet = 0

Tady uděláme jenom n operací, tedy složitost je O(n). Taky si můžeme rozmyslet, že tohle je určitě ideální řešení, protože už jen přečtení vstupní posloupnosti nám zabere čas O(n).


Jak poznám, že je moje složitost dost dobrá?

Pokud za proměnné dosadíš maximální možné hodnoty (ty budou napsané v zadání), získáš zhruba počet operací, které program provede na maximálně velkém vstupu. Průměrný dnešní počítač zvládne udělat řádově miliardu operací za sekundu. Pokud se dostaneš více jak do řádů miliard (tedy více než 109), tak už tvůj program pravděpodobně nestihne doběhnout včas, abys jeho výsledek ještě zvládl odevzdat.

Například to hloupé řešení naší úlohy v O(n³) by pro n=1000 trvalo asi pár sekund, ale řešení pro milion čísel byste se dočkali asi až za 31 let. To druhé řešení v O(n²) by 1000 čísel zvládlo za mikrosekundu, milion čísel ale asi za 16 minut. Tomu nejrychlejšímu řešení v O(n) by nedělala problém ani miliarda čísel, řešení byste měli za pár sekund.

Na závěr malý přehled často používaných složitostí:
  • O(1) – kostantní (například sečtení dvou čísel)
  • O(log n) – logaritmická (binární vyhledávání v setříděném poli)
  • O(n) – lineární (například vyhledávání v poli)
  • O(n²) – kvadratická (procházení všech dvojic)
  • O(n³) – kubická (všechny trojice)
  • O(2n) – exponenciální (počet všech podmnožin).

Za zmínku stojí také to, že ne každý příkaz v programu je doopravdy jen jeden příkaz s konstantní časovou složitostí. Když používáte nějaké funkce z vašeho programovacího jazyka, například nalezení hodnoty v poli nebo třídění, velmi se hodí vědět, co zhruba se skrývá pod kapotou a jakou to má svou časovou složitost. Třeba to nalezení hodnoty v poli bude obvykle trvat O(n), třídění zase O(n log n). To vám může ušetřit spoustu zbytečné práce s příliš pomalými programy.

Máš na to!

I ty můžeš vyhrát! Nebo to aspoň zkusit :)