Big-O apibūdina, kaip algoritmo veikimo laikas arba atminties naudojimas auga, kai įvesties dydis n auga. Jis nusako blogiausio atvejo asimptotinį elgesį, ignoruodamas konstantas ir žemesnės eilės narius.
Mums rūpi augimo greitis, ne tikslus žingsnių skaičius. O(2n + 5) yra paprasčiausiai O(n), nes kai n tampa didelis, konstantos ir mažesni nariai netenka svarbos.
| Big-O | Pavadinimas | Pavyzdys |
|---|
| O(1) | pastovi | masyvo indekso paieška |
| O(log n) | logaritminė | dvejetainė paieška |
| O(n) | tiesinė | sąrašo skenavimas |
| O(n log n) | tiesiškai-logaritminė | sumaišytas rūšiavimas |
| O(n²) | kvadratinė | įdėti ciklai |
| O(2ⁿ) | eksponentinė | nayvūs poaibiai |
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 slepia konstantas: O(n) algoritmas su didele konstanta gali pralaimėti O(n log n) su mažomis įvestimis. Taip pat sekite erdvės sudėtingumą, o ne tik laiko.
Big-O leidžia palyginti algoritmus nepalaužus jų ir nesirūpinant aparatine įranga.
Jis nuspėja, kurie sprendimai gyvena, kai įvestis auga iš šimtų į milijonus — skirtumas tarp savybės, kuri masteliuojasi, ir tos, kuri baigsis laiku.
Tai yra žodynas, kurį kiekvienas inžinierius naudoja samprotaudamas apie našumą.