Big-O popisuje, jak se doba běhu nebo paměť algoritmu zvyšuje se zvětšováním velikosti vstupu n. Zachycuje nejhorší asymptotické chování a ignoruje konstanty a členy nižšího řádu.
Zajímá nás tempo růstu, ne přesný počet kroků. O(2n + 5) je jednoduše O(n), protože jakmile n roste, konstanty a menší členy přestávají být důležité.
Knihovna IT otázek k pohovoru s podrobnými odpověďmi — od Junior po Senior.
Přispět| Big-O | Název | Příklad |
|---|
| O(1) | konstantní | vyhledání indexu v poli |
| O(log n) | logaritmický | binární vyhledávání |
| O(n) | lineární | prohledávání seznamu |
| O(n log n) | lineárně-logaritmický | řazení sloučením |
| O(n²) | kvadratický | vnořené smyčky |
| O(2ⁿ) | exponenciální | naivní podmnožiny |
def has_duplicate(nums):
for i in range(len(nums)): # outer loop: n
for j in range(i + 1, len(nums)): # inner loop: n
if nums[i] == nums[j]:
return True
return False
# nested loops -> O(n^2) time, O(1) space
Big-O skrývá konstanty: algoritmus O(n) s obrovskou konstantou může prohrát s O(n log n) na malých vstupech. Také sledujte složitost prostoru, nejen času.
Big-O vám umožňuje porovnávat algoritmy bez jejich spuštění nebo obav o hardware.
Předpovídá, která řešení přežijí, když vstupy rostou ze stovek na miliony — rozdíl mezi funkcí, která se škáluje, a jednou, která překročí časový limit.
Je to slovník, který používá každý inženýr k uvažování o výkonu.