Big-O keerukuse uurija

Vaata, kuidas algoritmide keerukusklassid kasvavad sisendi suuruse N suurenedes.

Näidisarvutus — Big-O keerukuse uurija

O(1)	1
O(log N)	7
O(N)	100
O(N log N)	664
O(N²)	10 000

Need on väärtused, mida kalkulaator lehe avamisel näitab. Muuda ülal mõnda sisendit, et need ümber arvutada.

Interaktiivse simulatsiooni laadimine...

Õppetund

Teooria — Big-O keerukuse uurija

Big-O on kasvu ülempiir, mitte aja mõõt. Väitmine, et algoritm on O(N²), tähendab, et alates teatud sisendi suurusest jääb selle töö alla fikseeritud N² kordse — see ei ütle midagi sekundite ega üldse midagi väikeste sisendite kohta.

Mida iga sümbol tähendab

N: sisendi suurus — mitu elementi algoritmile antakse. See on ülal määratud arv vahemikus 2 kuni 1 000 000.
f(N): selle suuruse juures tegelikult tehtud töö, loendatuna sekundite asemel abstraktsetes operatsioonides.
c: konstantne kordaja, mida tähistus tohib varjata. Väide on f(N) ≤ c·g(N); c võib olla 2 või 2000 ja see on täpselt see info, mille Big-O eirab.
n₀: suurus, millest alates piir peab kehtima. Alla n₀ võivad klassid paikneda mis tahes järjekorras, mistõttu ülaltoodud viis arvu väikese N korral kokku koonduvad.

Kust valem tuleb

Alusta väitest, mida on vaja täpsustada: töö f(N) ei kasva lõpuks kiiremini kui mingi võrdlusfunktsioon g(N).
“Mitte kiiremini” peab taluma konstantset tegurit, sest sisemise tsükli optimeerimine muudab konstanti, mitte kuju. Seega lubame kordajat: f(N) ≤ c·g(N).
Ja “lõpuks” peab andma andeks väikesed sisendid, kus võib juhtuda mida tahes. Nõua võrratust alles siis, kui N ≥ n₀. Kokkuvõttes: f(N) = O(g(N)) tähendab, et eksisteerivad mingid c > 0 ja n₀ selliselt, et f(N) ≤ c·g(N) iga N ≥ n₀ korral.

Kuidas nähtut lugeda

Viis rida kujutavad ühte sisendi suurust viie kasvuklassi kaudu, kus iga konstant on seatud väärtusele 1 — seega on need operatsioonide arvud, mitte täitmisajad. Vaikimisi valitud N = 100 korral näitavad need väärtusi 1, 7, 100, 664 ja 10,000. Logaritm on alusel 2: log₂ 100 ≈ 6.64, mistõttu kuvab O(log N) arvu 7 ja O(N log N) arvu 664, mitte 700.

Eeldab: Et üks operatsioon maksab sama palju kui mis tahes teine ning et arv on täpne, mitte mõõdetud. See muudabki võrdluse selgeks ja samavõrra abstraktseks — mälupöörduste mustrid, vahemälu käitumine ja ketas jäävad sellest mudelist välja ning reaalsel riistvaral otsustavad just need tavaliselt, kumb kahest algoritmist võidab.
Ei kehti, kui: Piir ei luba midagi allpool n₀ väärtust ning seda saab otse jälgida: seadista N = 2 ja viis klassi näitavad 1, 1, 2, 2 ja 4 — peaaegu eristamatud. Tähistuse garanteeritud järjekord ilmneb alles siis, kui N on suur, mistõttu võib väikese konstandiga O(N²) meetod võita O(N log N) meetodit iga sisendi puhul, mis sul tegelikult ette tuleb.

Kui kasv jätab optimeerimise jalgu 🖖

Big-O kirjeldab, kuidas töö maht kasvab sisendi suuruse kasvades. Üksik tsükkel kasvab enam-vähem N-iga, pesastatud tsüklid sageli N²-ga ja hargnev rekursioon võib kasvada eksponentsiaalselt. Oluline õppetund on skaala: väikese N juures näevad paljud lähenemised sarnased välja, kuid suurema N juures domineerib täitmisaega kasvuklass.

Kahekordistamise test 🖖

Kõige selgemini tajub kasvuklassi, kui sisendit kahekordistada ja jälgida, mis tööhulgaga juhtub. O(log N) korral see peaaegu ei muutu — kahendotsing leiab ühe elemendi miljoni seast umbes 20 võrdlusega. O(N) korral töö kahekordistub ja O(N²) korral neljakordistub. Liiguta selles tööriistas N-i ja vaata, kuidas vahed kasvavad nähtamatust tohutuks.

Kui kiirem klass kaotab 🖖

Madalam kasvuklass ei taga kiiremat programmi. Arvutiteadlased nimetavad erandeid galaktilisteks algoritmideks: parema Big-O-ga meetodid, mille peidetud konstanttegur on nii tohutu, et nad edestavad lihtsamaid meetodeid alles sisendite juures, mis on suuremad kui miski füüsilises universumis. Mitut rekordilist maatriksite korrutamise algoritmi ei kasutata praktikas just sel põhjusel — Big-O jätab vaikimisi kõrvale konstandid, mis tegeliku kiiruse määravad.

Ülesanne täielikult lahendatud

Koht, kus avaneb kuristik N log N ja N ² vahel 5 sammu
Kui N = 100, näitab paneel väärtust 664 avaldisele N log N ja 10 000 avaldisele N². See on vaid viieteistkordne tegur — vaevalt kuristik, mida keerukusklassidelt oodatakse. Arvuta välja, kus see kuristik tegelikult avaneb.
1. Alusta neist kahest arvust. log₂ 100 on 6,6439, seega N log₂ N on 664 ja N² on 10 000.
  
  $N lo g_{2} N = 100 \times 6.6439 = 664, N^{2} = 10000$
2. Nendevaheline suhe ei ole konstantne ja see ongi keerukusklasside kogu mõte. Jagamisel taandub N ühe korra välja, jättes järele N/log N — suuruse, mis kasvab piiramatult, kuid aeglaselt.
3. Kui N = 100, on see 15,1. See on reaalne, kuid mitte avaldav: viieteistkordne kiirendus on sellist liiki asi, mille võib anda parem konstanditegur — mis on täpselt see põhjus, miks jõudlustestid väikestel sisenditel eksitavad.
  
  $\frac{N ^{2}}{N lo g _{2} N} = \frac{N}{lo g _{2} N} = \frac{100}{6.6439} = 15.1$
4. Nüüd võta sisendiks miljon. Logaritm on vaevalt liikunud — 6,6-lt 19,9-le ehk kolm korda —, samal ajal kui N on kasvanud kümnetuhandekordseks. Suhe on nüüd 50 172.
  
  $N = 1 0^{6} : \frac{N}{lo g _{2} N} = \frac{1 0 ^{6}}{19.93} = 50172$
5. Ja see ei pöördu kunagi tagasi. Avaldise N/log N tuletis on positiivne iga N korral, mis on suurem kui e, seega ei ole olemas ühtegi sisendi suurust, millest alates ruutalgoritm sellele järele jõuaks.
  
  $\frac{d}{d N} (\frac{N}{lo g _{2} N}) > 0 for N > e ⟹ the gap only widens$
Vastus

Tööriist väljastab väärtused 664 ja 10 000, kui N = 100. Meeldejätmist vääriv arv on aga teine: miljoni juures on need kaks kõverat teineteisest 50 172 võrra kaugel. Keerukusklassid ei käi saja elemendi kohta ning nende võrdlemine seal on tüüpiline viis veenda ennast valima valet algoritmi — viieteistkordne vahe näib asjana, mida kiirem programmeerimiskeel võiks tasa teha. Nihuta liugurit ülespoole ja vaata, kuidas suhe kaasa liigub. See on ühtlasi põhjus, miks logaritmi praktikas nii sageli eiratakse: see kasvas kolm korda, kui sisend kasvas kümne tuhat korda.

$\frac{N ^{2}}{N lo g N} = \frac{N}{lo g N} : 15 \times at 100, 50172 \times at 1 0^{6}$

Õpitee

Loe tööd, mitte sekundeid

Viib edasi sorting-race

Allikad (1)

The definition the lesson states, and the case for using it carefully: D. E. Knuth, “Big Omicron and big Omega and big Theta.” ACM SIGACT News 8, 18–24, 1976.

42Mathi meeskond · Uuendatud 2026-06-10

Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud. Toimetamispõhimõtted · Parandused

Kõik Arvutustehnika õppetunnid →

Näiteülesanded

Väike N=20 - Kõik kõverad N=20 juures
N=1000 - N=1000: polünomiaalsed kõverad hakkavad lahknema
Log-skaala - Logaritmiline skaala toob esile kasvuerinevused
Peidetud konstandid - Kui c=50, ristuvad 50N log N ja N² ligikaudu N=439 juures