AlegsaOnline.com

Big O notacija (Didysis O): algoritmų sudėtingumo apibrėžimas

Sužinokite, kas yra Big O (Didysis O) notacija: algoritmų sudėtingumo, laiko ir atminties vertinimas, blogiausio atvejo analizė ir praktiniai pavyzdžiai.

Autorius: Leandro Alegsa

12-01-2026

Big O (Didysis O) – tai būdas palyginti algoritmus pagal tai, kiek jie reikalauja laiko ir atminties vykdymo metu. Big O nurodo, kaip algoritmo resursų poreikis auga priklausomai nuo duomenų dydžio (dažniausiai žymimo n). Tai leidžia įvertinti algoritmo efektyvumą nepriklausomai nuo konkrečios techninės įrangos.

Istoriškai Didįjį O pirmąkart panaudojo Paulas Bachmannas (1837–1920) 1896 m., o vėliau šią notaciją išpopuliarino Edmundas Landau (1877–1938). Dėl to kartais ši notacija vadinama Landau simboliais. Ji padeda priskirti problemas tam tikroms sudėtingumo klasėms pagal reikiamus resursus.

Intuityvus paaiškinimas

Big O nurodo funkcijos augimo tvarką — viršutinę ribą (didžiausią galimą dydį) kai n didėja. Kitaip tariant, jis atsako į klausimą: „Kaip ilgai (ar kiek atminties) užtruks algoritmas, kai įvesties dydis auga?“ Big O dažniausiai apibrėžia blogiausią atvejį (worst case), todėl suteikia konservatyvų, patikimą vertinimą.

"Big O" užrašas pavadintas pagal terminą "funkcijos tvarka", kuris reiškia funkcijų augimą. Big O užrašas naudojamas funkcijos augimo greičio viršutinei ribai (didžiausiam įmanomam dydžiui) rasti, t. y. nustatomas ilgiausias laikas, per kurį įvestis bus paversta išvestimi. Tai reiškia, kad algoritmą galima sugrupuoti pagal tai, kiek laiko jis gali užtrukti blogiausiu atveju, kai kiekvieną kartą bus pasirinktas ilgiausias kelias.

"Big O" - tai išraiška, kuria nustatomas blogiausio scenarijaus vykdymo laikas, parodantis, koks yra algoritmo efektyvumas, nepaleidžiant programos kompiuteryje. Tai naudinga ir todėl, kad skirtinguose kompiuteriuose gali būti skirtinga techninė įranga, todėl jai atlikti gali prireikti skirtingo laiko. Kadangi "Big O" visada numato blogiausią atvejį, galima nuosekliai išmatuoti greitį: nepriklausomai nuo jūsų techninės įrangos, "O ( 1 )" {\displaystyle O(1)} $O(1)$ visada bus baigtas greičiau nei "O ( n ! )" {\displaystyle O(n!)}, $O(n!)$ nes jų efektyvumas skiriasi.

Formalus apibrėžimas

Sakome, kad f(n) = O(g(n)), jei egzistuoja teigiama konstanta C ir skaičius n0 tokie, kad visiems n ≥ n0 yra f(n) ≤ C·g(n). Tai reiškia: kai n tampa pakankamai didelis, f(n) neauga greičiau nei konstantiniu koeficientu padauginta g(n).

Dažniausiai pasitaikančios sudėtingumo klasės (nuo geriausios iki blogiausios)

O(1) – konstantinė: vykdymo laikas nekinta augant n (pvz., prieiga prie masyvo elemento).
O(log n) – logaritminė: pvz., binarinė paieška suskaidant paieškos sritį per pusę.
O(n) – linijinė: pvz., vienas ciklas per visus elementus.
O(n log n) – daugumai efektyvių rūšiavimo algoritmų (pvz., merge sort, heap sort).
O(n^2) – kvadratinė: dažnai gaunama iš dviejų įdėtų ciklų (pvz., paprastas rūšiavimas).
O(2^n) – eksponentinė: dažnai susijusi su visų galimų kombinacijų tikrinimu.
O(n!) – faktorialinė: labai lėti algoritmai (pvz., permutacijų generavimas be heuristikų).

Pavyzdžiai ir taisyklės analizėje

Vienas ciklas per n elementų: O(n).
Dviejų įdėtų ciklų, kiekvienas nuo 1 iki n: O(n^2).
Konsektyvūs žingsniai: O(f(n) + g(n)) → imama didžiausia iš abiejų (pvz., O(n) + O(n^2) = O(n^2)).
Multiplikacija priklausoma nuo įdėtos struktūros: pvz., už kiekvieno iš n elementų atliekama log n operacija → O(n log n).
Ignoruojami konstantiniai koeficientai ir žemesnės eilės terminai: O(2n) = O(n), O(n + log n) = O(n).

Laiko ir atminties sudėtingumas

Big O gali taikyti ne tik vykdymo laikui, bet ir atminties naudojimui (space complexity). Pvz., algoritmas, kuris laikinai saugo papildomą masyvą dydžio n, turi O(n) atminties sudėtingumą.

Geriausias, vidutinis ir blogiausias atvejai

Analizė gali skirtis priklausomai nuo atvejo:

Best case – geriausias atvejis (pavyzdžiui, paieška randa elementą pirmame žingsnyje).
Average case – vidutinis atvejis (reikia apskaičiuoti vidutinį vykdymo laiką pagal visus galimus įvesties atvejus).
Worst case – blogiausias atvejis (dažnai naudojamas praktikoje, kadangi tai saugiausias įvertinimas).

Amortizuota sudėtingumo analizė

Kai kurios duomenų struktūros (pvz., dinaminių masyvų išplėtimas arba HashMap operacijos) turi amortizuotą laiką: pavienės operacijos gali būti brangios, bet ilgalaikė vidutinė kaina vienai operacijai yra mažesnė. Tokiu atveju nurodoma amortizuota sudėtingumo riba, pvz., push amortizuotai O(1).

Praktiniai patarimai, kaip skaičiuoti Big O

Suskaičiuok pagrindinius veiksmus arba ciklus, kurie auga su n.
Pabandyk supaprastinti: atsisakyk pastovių koeficientų ir mažesnės eilės terminų.
Analizuok rekursijas per rekurenčiųjų lygtis (recurrence), naudok Master teoremą, kai tinka.
Atkreip dėmesį į duomenų struktūrą – pasirinkimas (masyvas, sąrašas, rinkinys, žemėlapis) gali pakeisti sudėtingumą.

Trumpi pavyzdžiai

Lineinė paieška: for(i=0;i
Dviejų lygių ciklas: for(i=0;i
Binarinė paieška (rūšiuotame sąraše): O(log n).
Merge sort: O(n log n) laiko ir O(n) papildomos atminties.

Apibendrinant: Big O yra paprasta, bet galinga priemonė, leidžianti objektyviai palyginti algoritmus pagal jų elgesį augant duomenų kiekiui. Ji neatsako į visus praktinius klausimus (pvz., konkrečios mašinos greitį arba konstantų poveikį mažiems n), tačiau suteikia aiškų ir formalų būdą įvertinti ir pasirinkti efektyvesnius sprendimus.

Pavyzdžiai

Visuose toliau pateikiamuose pavyzdžiuose naudojamas "Python" kalba parašytas kodas. Atkreipkite dėmesį, kad tai nėra išsamus "Big O" tipų sąrašas.

Nuolatinis

O ( 1 ) {\displaystyle O(1)} $O(1)$ . Visada užtrunka tiek pat laiko, nepriklausomai nuo įvesties. Pavyzdžiui, paimkime funkciją, kuri priima sveikąjį skaičių (vadinamą x) ir grąžina dvigubą jo vertę:

def double(x): return x * 2 #Grąžinama x vertė, padauginta iš 2

Priėmusi įvestį, ši funkcija visada atliks vieną žingsnį, kad grąžintų išvestį. Jis yra pastovus, nes visada užtruks tiek pat laiko, taigi jis yra O ( 1 ) {\displaystyle O(1)} $O(1)$ .

Linijinis

O ( n ) {\displaystyle O(n)} $O(n)$ . Padidėja priklausomai nuo įvesties dydžio, išreikšto n {\displaystyle n} . Tarkime, kad funkcija priima n ir grąžina kiekvieną skaičių nuo 1 iki n:

def count(n): i = 1 #Sukurkite skaitiklį, pavadintą "i", kurio reikšmė yra 1 while i <= n: #Kol i yra mažesnis arba lygus n print(i) #Spausdinkite i reikšmę i = i + 1 #Nustatykite i kaip "i + 1 reikšmę"

Jei įvestume vertę 5, tuomet būtų išvedama 1 , 2 , 3 , 4 , 5 {\displaystyle 1,2,3,3,4,5} $1,2,3,4,5$ , o tam, kad būtų užbaigti 5 ciklai, reikia 5 ciklų. Panašiai, jei įvestume 100, būtų išvesta 1 , 2 , 3...98 , 99 , 100 {\displaystyle 1,2,3...98,99,100} $1,2,3...98,99,100$ , todėl reikėtų atlikti 100 ciklų. Jei įvestis yra n {\displaystyle n}, algoritmo veikimo laikas kiekvieną kartą yra lygiai n {\displaystyle n} ciklų, todėl jis yra O ( n ) {\displaystyle O(n)} $O(n)$ .

Faktorinis

O ( n ! ) {\displaystyle O(n!)} $O(n!)$ . Didėja faktoriniais dydžiais, o tai reiškia, kad laiko sąnaudos didėja kartu su įvesties dydžiu. Pavyzdžiui, tarkime, norime aplankyti penkis pasaulio miestus ir norime pamatyti visus įmanomus išsidėstymus (permutacijas). Algoritmas, kurį galėtume parašyti naudodami Python itertools biblioteką, yra toks:

import itertools #Importuokite itertools biblioteką cities = ['London', 'Paris', 'Berlin', 'Amsterdam', 'Rome'] #Mūsų pasirinktų miestų masyvas def permutations(cities): #Kaip įvestį imant miestų masyvą: for i in itertools. permutations(cities): #Kiekvienai mūsų elementų permutacijai (priskirtai kintamajam "i") print(i) #Išėjimas i

Šis algoritmas apskaičiuos kiekvieną unikalią mūsų miestų permutaciją ir ją išves. Išvesties pavyzdžiai bus tokie:

("Londonas", "Paryžius", "Berlynas", "Amsterdamas", "Roma") ("Londonas", "Paryžius", "Berlynas", "Roma", "Amsterdamas") ("Londonas", "Paryžius", "Amsterdamas", "Berlynas", "Roma") ... ("Roma", "Amsterdamas", "Paryžius", "Berlynas", "Londonas") ("Roma", "Amsterdamas", "Berlynas", "Londonas", "Paryžius") ("Roma", "Amsterdamas", "Berlynas", "Paryžius", "Londonas")

Šiuo atveju mūsų įvesties sąrašas yra 5 elementų ilgio, o su kiekvienu pasirinkimu mūsų likusios galimybės sumažėja 1. Kitaip tariant, mūsų 5 įvestys pasirenka 5 × 4 × 3 × 2 × 1 {\displaystyle 5\times 4\times 3\times 2\times 1} $5\times 4\times 3\times 2\times 1$ elementų (arba 5 ! {\displaystyle 5!} $5!$ ). Jei mūsų įvestis yra n {\displaystyle n} miestų ilgio, tai išėjimų skaičius yra n ! {\displaystyle n! } $n!$ ; kitaip tariant, jei pereisime per kiekvieną permutaciją, reikės O ( n ! ) {\displaystyle O(n!)} $O(n!)$ ciklų, kad ją užbaigtume.

Little-o užrašas

Griežtesnė "Didžiojo O" versija yra "little-o". Skirtumas tarp big O ir little-o yra tas, kad little-o yra griežta viršutinė riba: nors O ( n ) {\displaystyle O(n)} reiškia, kad $O(n)$ užbaigimo laikas, atsižvelgiant į įvesties dydį, padidės iki šios maksimalios ribos, o ( n ) {\displaystyle o(n)} reiškia, kad $o(n)$ užbaigimo laikas paprastai neviršys šios ribos. Kitaip tariant, Big O daro prielaidą, kad kiekviena kilpa eis ilgiausiu keliu ir procesas užtruks kuo ilgiau, o little-o realiau vertina faktinį vykdymo laiką; jei kilpų skaičius grindžiamas šešiabriaunio kauliuko metimu, Big O visada darys prielaidą, kad iškrito 6, o little-o atsižvelgs į vienodą tikimybę, kad iškrito kiti skaičiai.

Klausimai ir atsakymai

K: Kas yra "Big O" užrašas?

A: Didžioji O notacija - tai būdas palyginti skirtingų funkcijų augimo tempus, dažnai naudojamas skirtingų algoritmų efektyvumui palyginti, apskaičiuojant, kiek atminties ir laiko reikia jiems atlikti. Jis taip pat gali būti naudojamas nustatyti, kiek sudėtinga yra problema.

Klausimas: Kas pirmasis panaudojo šį užrašą?

A: Matematikas Paulas Bachmannas (1837-1920) 1896 m. savo knygoje "Analytische Zahlentheorie" pirmasis panaudojo šį užrašą.

K: Ką reiškia "Big O"?

A: Big O reiškia "funkcijos tvarką", kuri reiškia funkcijų augimo greitį.

K: Kaip naudojamas Big O?

A: Big O užrašas naudojamas funkcijos augimo greičio viršutinei ribai (didžiausiam įmanomam dydžiui) rasti, t. y. nustatomas ilgiausias laikas, per kurį įvestis virsta išvestimi. Tai reiškia, kad algoritmus galima sugrupuoti pagal tai, kiek laiko jie užtrunka blogiausiu atveju, kai kiekvieną kartą bus pasirinktas ilgiausias kelias.

K: Kas yra Landau simboliai?

A: Landau simboliai reiškia "Big O" notaciją, pavadintą Edmundo Landau (1877-1938), kuris išpopuliarino šią notaciją, vardu.

K: Kodėl Big O yra naudingas?

A:Big O leidžia mums matuoti greitį nepaleidžiant programų kompiuteriuose, nes jis visada numato blogiausius scenarijus, todėl yra nuoseklus, nepriklausomai nuo kompiuterių techninės įrangos skirtumų. Jis taip pat parodo, koks yra algoritmo efektyvumas, nereikalaujant, kad jis būtų paleistas kompiuteryje.