Výpočtová zložitosť a porovnania

• toto

První příklad má dle mého složitost $O(N^2)$. Za použití nějaké formy Setu, nebo Dictionary to jde zjednodušit na $O(N)$. Např v syntaxi pythonu:

Wanted  = { } 

for x in a:
    if x in Wanted: return True
    Wanted.add(sucet-x)

return False

Vnořené cykly se délkou násobí. V nejhorším případě tedy "Pro každý prvek pole projdu všechny po něm následující", tedy $N*(N-1)/2$ kroků, tedy výše zmíněná složitost.

Když si rozmyslíme druhý příklad, vidíme, že uvedený algoritmus provádí řádově $O(N)$ porovnání. Zkus si to nakreslit pro pár počtů... pro 8 dostanu 7 porovnání, pro 10 dostanu 11 a pro 5 dostanu 5. Nejlépe to dopadne pro $2^n$ prvků.

Nerekurzivní algoritmus provede přesně $n-1$ porovnání - první s ničím neporovnává, každý další porovnává s aktuálním maximem.