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

Nebo alespoň želvu?

Složitost

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) 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, některé mu dají zabrat víc.

Budeme tedy určovat rychlost programů a algoritmů podle toho, kolik jednoduchých operací musí počítač provést, aby vydal výsledek. 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é či čtení jednoho znaku ze vstupu. 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 počtu čísel 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 4 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 oproti zanedbatelné, tedy složitost je O(n²).

Hlavní myšlenkou pro toto řešení je úvaha, kde může úsek začínat nebo končit. Můžeme si rozmyslet, že pokud máme nějakou posloupnost se součtem a před ní nebo za ní je souvislá posloupnost, která má kladný součet, potom můžeme naši posloupnost o tuto posloupnost rozšířit. Takto procházíme prvky od začátku ke konci, vždy přičteme další prvek a porovnáme náš součet s maximálním. Pokud součet klesne pod nulu, tak součet zahodíme a začneme opět od nuly (součet nastavíme na 0).

  // 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 :)