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.