Big O notatsioon — definitsioon, ajakompleksus ja algoritmide võrdlus

Avasta Big O notatsioon: selge definitsioon, ajakompleksuse selgitus ja algoritmide praktiline võrdlus koos näidete ja optimeerimisnõuannetega.

Autor: Leandro Alegsa

20-10-2025 22:30

Big O Notation on viis algoritmide võrdlemiseks, mis kirjeldab, kuidas algoritmi tööaeg (ja sageli ka mälu kasutus) kasvab koos sisendi suuruse kasvuga. Big O väljendab algoritmi asümptootilist ülemist piiri ehk seda, kui kiiresti kasvab ressursikulu suurte sisendite korral — see aitab hinnata algoritmi skaleeritavust ilma programmi käivitamata.

Big O märkust kasutatakse sageli probleemi keerukuse määramisel, mida nimetatakse ka probleemi keerukusklassiks. Matemaatik Paul Bachmann (1837–1920) kasutas sarnast tähist juba oma raamatu "Analytische Zahlentheorie" teises väljaandes 1896. aastal; Edmund Landau (1877–1938) populariseeris seda ja seetõttu räägitakse vahel ka Landau sümbolitest.

Mis täpselt Big O tähendab?

Big O kirjeldab funktsiooni kasvukiiruse ülemist piiri. Praktiliselt tähendab see, et kirjeldatakse, kui kiiresti vajalike operatsioonide arv (või mälukasutus) suureneb sisendi suuruse n kasvades, jättes tähelepanuta konstantvõtmed ja madalama järgu liikmed. Näiteks funktsioon f(n)=3n+5 on Big O järgi O(n), sest domineerivaks liikmeks on lineaarne osa n ja konstantid ei muuda kasvu asümptootikat.

Halvim, keskmine ja parim juhu keerukus

Halvim juhtum (worst-case) — Big O iseloomustab sageli seda, kui kaua algoritm võib maksimaalselt aega võtta (näiteks sorteerimine, kui sisend on juba halvimal võimalikul korral). See on kasulik, sest annab garantii jõudluse üle erineval riistvaral ja sisenditel.
Keskmine juhtum (average-case) — mõnikord huvitab oodatav käitumine juhuslike sisendite korral.
Parim juhtum (best-case) — kui sisend on kõige soodsam, kui aega kulub minimaalselt.

Miks Big O on riistvarast sõltumatu?

Big O vaatleb vaid opsioonide arvu kui funktsiooni n-ist, mitte üksikute operatsioonide täpset kestust. Seetõttu on see kasulik abstraktne mõõde: erinevatel riistvaradel võivad olla erinevad konstantsed ajakulud, kuid asümptootiline kasv (kasvutempo) jääb samaks. Näiteks O ( 1 ) {\displaystyle O(1)} $O(1)$ lõpeb alati kiiremini kui O ( n ! ) {\displaystyle O(n!)} $O(n!)$ , sest nende kasvuastmed on fundamentaalselt erinevad.

Levinumad keerukusklassid ja lihtsed näited

O(1) — konstantne aeg. Näide: massiivi elementile indeksiga ligipääs (array[index]).
O(log n) — logaritmiline (nt binaarotsing tasandatud sorteeritud massiivis).
O(n) — lineaarne (üks tsükkel läbi kõigi elementide).
O(n log n) — tüüpiline hea sorteerimisaeg (merge sort, heapsort, kiiruselt tavaliselt parem kui n^2 suuremate n korral).
O(n^2) — kvadraatne (kahekordsed pesastatud tsüklid, nt bubble sort, simple lähim paar algoritmid ilma optimeerimiseta).
O(2^n) — eksponentsiaalne (nt rekursiivsed lahendused kõikide alamhulkade läbimiseks, kui ei kasuta dünaamilist programmeerimist).
O(n!) — faktoriaalne (nt kõikide permutatsioonide genereerimine — permutatsioonide arv kasvab väga kiiresti).

Kuidas Big O arvutatakse — mõned reeglid

Ignoreeri konstandid: f(n)=5·n on O(n).
Pane tähele domineerivat terminit: f(n)=n^2+100n+10 on O(n^2).
Kui mitu samm on järjest, siis liida: O(f)+O(g)=O(max(f,g)).
Kui sammud on pesastunud (sõltuvad üksteisest), siis korruta: näiteks kaks pesastatud n-pikkust tsüklit annavad O(n·n)=O(n^2).

Ruumikeerukus (space complexity)

Lisaks ajakompleksusele kirjeldab Big O ka mälukasutust — kui palju lisamälu algoritm vajab suhteks sisendi suurusega n. Näiteks algoritm, mis kasutab paarisumma leidmiseks ainult mõnda konstantset muutujat, on O(1) ruumikasutuselt, samas kui algoritm, mis loob koopia andmetest või tabeli suurusega n, on O(n).

Piirangud ja praktilised märkused

Big O on asümptootiline ja keskendub suurtele n-dele — väikeste sisendite puhul võivad konstantsed tegurid ja praktilised optimeeringud määrata tegeliku jõudluse.
Big O ei ütle, milline algoritm on "parem" igas olukorras — oluline on ka ruumikasutus, stabiilsus sorteerimisel, keerukuse lihtsus ja tegelikud konstantsed tegurid.
Keskmise ja parima juhtumi analüüs võib olla oluline (nt quicksort on keskmiselt O(n log n), kuid halvimal juhul O(n^2) ilma pivot-optimeerimiseta).

Kokkuvõte ja soovitused

Big O notatsioon on võimas tööriist algoritmide ja andmestruktuuride võrdlemiseks ning aitab valida skaleeruvaid lahendusi. Õppides äratundma tüüpilisi keerukusmustreid (constant, logarithmic, linear, n log n, quadratic, exponential, factorial) ja rakendades reegleid (ignoreeri konstante, keskendu domineerivale terminile), saad teha läbi mõeldud valikuid nii akadeemilistes ülesannetes kui ka reaalse maailma tarkvaraarenduses. Samal ajal meenuta praktikas alati ka mõõtmist ja profiliseerimist — Big O annab teoreetilise piiri, kuid mitte alati täpset reaalmaailma käitumist.

Näited

Järgnevad näited kasutavad kõik Pythonis kirjutatud koodi. Pange tähele, et see ei ole täielik nimekiri Big O tüüpidest.

Pidev

O ( 1 ) {\displaystyle O(1)} $O(1)$ . Võtab alati sama palju aega, olenemata sisendist. Võtame näiteks funktsiooni, mis võtab vastu täisarvu (nimega x) ja tagastab selle kahekordse väärtuse:

def double(x): return x * 2 #Return the value of x times 2

Pärast sisendi vastuvõtmist teeb see funktsioon alati ühe sammu, et tagastada väljund. See on konstantne, sest see võtab alati sama palju aega, seega on see O ( 1 ) {\displaystyle O(1)} $O(1)$ .

Lineaarne

O ( n ) {\displaystyle O(n)} $O(n)$ . Suureneb vastavalt sisendi suurusele, mida esindab n {\displaystyle n} . Oletame, et funktsioon võtab vastu n ja tagastab iga arvu 1 kuni n:

def count(n): i = 1 #Loo loendur nimega "i" väärtusega 1 while i <= n: #While i on väiksem või võrdne n-ga print(i) #Trükki i väärtus i = i + 1 #Redefineeri i kui "väärtus i + 1"

Kui me sisestaksime väärtuse 5, siis oleks väljundiks 1 , 2 , 3 , 4 , 5 {\displaystyle 1,2,3,4,5} $1,2,3,4,5$ , mis nõuab 5 tsüklit. Samamoodi, kui me sisestaksime 100, annaks see tulemuseks 1 , 2 , 3...98 , 99 , 100 {\displaystyle 1,2,3...98,99,100} $1,2,3...98,99,100$ , mis nõuab 100 tsüklit. Kui sisend on n {\displaystyle n}, siis on algoritmi tööaeg iga kord täpselt n {\displaystyle n} silmust, seega on see O ( n ) {\displaystyle O(n)} $O(n)$ .

Faktorija

O ( n ! ) {\displaystyle O(n!)} $O(n!)$ . Suureneb faktoriaalselt, mis tähendab, et ajakulu suureneb massiivselt koos sisendiga. Näiteks ütleme, et soovime külastada viit linna üle maailma ja tahame näha kõiki võimalikke järjestusi (permutatsioone). Algoritm, mille võiksime kirjutada Pythoni itertools raamatukogu kasutades, on järgmine:

import itertools #Import itertools library cities = ['London', 'Paris', 'Berlin', 'Amsterdam', 'Rome'] #Massiivi meie valitud linnadest def permutations(cities): #Võttes sisendiks linnade massiivi: for i in itertools. permutations(cities): #Kõigi meie elementide permutatsiooni jaoks (määratud muutujale "i") print(i) #väljund i

See algoritm arvutab iga meie linnade unikaalse permutatsiooni ja seejärel väljastab selle. Näited väljunditest on järgmised:

("London", "Pariis", "Berliin", "Amsterdam", "Rooma") ("London", "Pariis", "Berliin", "Rooma", "Amsterdam") ("London", "Pariis", "Amsterdam", "Berliin", "Rooma") ... ("Rooma", "Amsterdam", "Pariis", "Berliin", "London") ("Rooma", "Amsterdam", "Berliin", "London", "Pariis") ("Rooma", "Amsterdam", "Berliin", "Pariis", "London")

Siin on meie sisestusnimekiri 5 elementi pikk ja iga valiku puhul vähenevad meie ülejäänud valikud 1 võrra. Teisisõnu, meie 5 sisendit valivad 5 × 4 × 3 × 2 × 1 {\displaystyle 5\times 4\times 3\times 2\times 1} $5\times 4\times 3\times 2\times 1$ elementi (või 5 ! {\displaystyle 5!} $5!$ ). Kui meie sisend on n {\displaystyle n} linna pikkune, siis on väljundite arv n ! {\displaystyle n! } $n!$ ; teisisõnu, eeldades, et me läbime iga permutatsiooni, vajame selle lõpetamiseks O ( n ! ) {\displaystyle O(n!)} $O(n!)$ silmust.

Little-o Notation

Big O rangem versioon on little-o. Suure O ja little-o erinevus seisneb selles, et little-o on range ülempiir: kui O ( n ) {\displaystyle O(n)} $O(n)$ tähendab, et lõpetamise aeg suureneb sisendi suuruse põhjal selle maksimumini, siis o ( n ) {\displaystyle o(n)} $o(n)$ tähendab, et lõpetamise aeg jääb üldiselt alla selle aja. Teisisõnu, Big O eeldab, et iga silmus kulgeb kõige pikemat teed ja protsess võtab võimalikult kaua aega, samas kui little-o on tegeliku tööaja suhtes realistlikum; kui silmuste arv põhineb 6-kandilise täringu viskamisel, siis Big O eeldab alati, et viskatakse 6, samas kui little-o arvestab teiste numbrite viskamise võrdse tõenäosusega.

Küsimused ja vastused

K: Mis on Big O märkimine?

V: Big O notatsioon on viis erinevate funktsioonide kasvukiiruste võrdlemiseks, mida kasutatakse sageli erinevate algoritmide tõhususe võrdlemiseks, arvutades, kui palju mälu ja aega kulub nende täitmiseks. Seda saab kasutada ka selleks, et määrata, kui keeruline on probleem.

K: Kes kasutas seda notatsiooni esimesena?

V: Matemaatik Paul Bachmann (1837-1920) kasutas seda notatsiooni esimesena oma 1896. aastal ilmunud raamatus "Analytische Zahlentheorie".

K: Mida tähendab suur O?

V: Big O tähistab "funktsiooni järjestust", mis viitab funktsioonide kasvukiirusele.

K: Kuidas kasutatakse Big O-d?

V: Big O tähistust kasutatakse funktsiooni kasvukiiruse ülemise piiri (suurima võimaliku summa) leidmiseks, mis tähendab, et see arvutab välja pikima aja, mis kulub sisendi muutmiseks väljundiks. See tähendab, et algoritme saab rühmitada selle järgi, kui kaua neil kulub halvimal juhul, kus iga kord võetakse kõige pikem tee.

K: Mis on Landau sümbolid?

V: Landau sümbolid viitavad Big O notatsioonile, mis on nimetatud Edmund Landau (1877-1938) järgi, kes tegi selle notatsiooni populaarseks.

K: Miks on Big O kasulik?

V: Big O võimaldab meil mõõta kiirust, ilma et peaksime programme arvutites käivitama, kuna see eeldab alati halvimat stsenaariumi, mis teeb selle järjepidevaks sõltumata arvutite vahelistest riistvaralistest erinevustest. Samuti näitab see, kui tõhus on algoritm, ilma et seda tegelikult arvutis käivitataks.

Otsige