AlegsaOnline.com

Big O -merkintä (asymptoottinen suoritusaika): määritelmä ja esimerkit

Ymmärrä Big O -merkintä: määritelmä, historia ja selkeät esimerkit algoritmien aikavaativuuksista sekä pahimman tapauksen analyysista.

Tekijä: Leandro Alegsa

09-03-2026

Matematiikassa ja tietojenkäsittelytieteessä Big O -merkintä on tapa verrata eri funktioiden kasvunopeuksia. Sitä käytetään usein eri algoritmien tehokkuuden vertailuun, mikä tehdään laskemalla, kuinka paljon muistia tarvitaan ja kuinka paljon aikaa algoritmin suorittamiseen kuluu.

Big O -merkintää käytetään usein ongelman monimutkaisuuden määrittelyssä, jota kutsutaan myös ongelman monimutkaisuusluokaksi. Matemaatikko Paul Bachmann (1837-1920) käytti tätä merkintätapaa ensimmäisenä vuonna 1896 julkaistussa kirjansa "Analytische Zahlentheorie" toisessa painoksessa. Edmund Landau (1877-1938) teki merkintätavasta suositun. Tästä syystä kun puhutaan Landaun symboleista, viitataan tähän merkintätapaan.

Big O -notaatio on saanut nimensä "funktion järjestyksen" mukaan, joka viittaa funktioiden kasvuun. Big O -merkintätapaa käytetään funktion kasvunopeuden ylärajan (suurimman mahdollisen määrän) löytämiseen, mikä tarkoittaa, että se laskee pisimmän ajan, joka tarvitaan syötteen muuttamiseen tulosteeksi. Tämä tarkoittaa, että algoritmi voidaan ryhmitellä sen mukaan, kuinka kauan se voi kestää pahimmassa tapauksessa, jossa pisin reitti otetaan joka kerta.

Tarkemmin sanottuna annetaan kaksi positiivista funktiota f ( x ) {\displaystyle f(x)} f(x) ja g ( x ) {\displaystyle g(x)} $g(x)$ , sanomme, että f {\displaystyle f} on g {\displaystyle g} isossa O:ssa (kirjoitettuna f ∈ O ( g ) {\displaystyle f\in O(g)} $f\in O(g)$ ), jos tarpeeksi suurella x {\displaystyle x} , f ( x ) ≤ k ⋅ $f(x)\leq k\cdot g(x)$ jonkin vakion k {\displaystyle k} tapauksessa.

Big O on lauseke, joka määrittää pahimman mahdollisen skenaarion suoritusajan ja osoittaa, kuinka tehokas algoritmi on ilman, että ohjelmaa tarvitsee ajaa tietokoneella. Tämä on hyödyllistä myös siksi, että eri tietokoneissa voi olla erilainen laitteisto, ja siksi ne tarvitsevat eri määrän aikaa ohjelman suorittamiseen. Koska Big O olettaa aina pahimman tapauksen, se voi näyttää johdonmukaisen nopeuden mittauksen: laitteistosta riippumatta O ( 1 ) {\displaystyle O(1)} $O(1)$ valmistuu aina nopeammin kuin O ( n ! ) {\displaystyle O(n!)}. $O(n!)$ , koska niiden tehokkuus on erilainen.

Määritelmän selitys ja todistaminen käytännössä

Formaalisti sanotaan: f(n) ∈ O(g(n)), jos löytyy positiivinen vakio k ja luku n0 siten, että kaikilla n ≥ n0 pätee f(n) ≤ k·g(n). Käytännössä tämä tarkoittaa, että g(n) toimii ylärajana f(n):lle, kun n kasvaa riittävän suureksi.

Valitse sopiva g(n) — yleensä samaa tai korkeampaa kasvuluokkaa oleva funktio (esim. n, n^2, 2^n).
Määritä vakio k ja leikkauspiste n0, jotka tekevät epäyhtälöstä totta kaikilla n ≥ n0.
Todista epäyhtälö yksinkertaisilla arvioilla (esim. pienempi termi ≤ suurempi termi, polynomien suurompia termejä verrataan).

Esimerkki: f(n)=3n+2. Valitaan g(n)=n. Silloin 3n+2 ≤ 5n aina kun n ≥ 2. Voimme siis valita k=5 ja n0=2, joten 3n+2 ∈ O(n).

Toinen esimerkki: f(n)=n^2+n. Valitaan g(n)=n^2. Silloin n^2+n ≤ n^2 + n^2 = 2n^2 aina kun n ≥ 1. Voimme siis valita k=2 ja n0=1, joten n^2+n ∈ O(n^2).

Yleisimpiä kasvuluokkia ja käytännön esimerkit

O(1) — vakioaika: esimerkiksi arvon hakeminen taulukon indeksistä.
O(log n) — logaritminen: esimerkiksi binäärihaku järjestetyssä taulukossa.
O(n) — lineaarinen: esimerkiksi läpikäynti listan kaikille alkioille.
O(n log n) — yleinen tehokas lajittelun aikavaativuus, esim. mergesort tai heapsort.
O(n^2) — kvadraattinen: esimerkiksi yksinkertainen kaksinkertainen silmukka (bubble sort, insertion sort huonossa tapauksessa).
O(2^n) — eksponentiaalinen: esim. kaikki osajoukot generointi ilman optimointeja.
O(n!) — faktoriaalinen: täydellinen permutaatioiden läpikäynti (esim. bruteforce Travelling Salesman -ongelma).

Sääntöjä ja nyrkkisääntöjä

Pienemmät termit voi jättää: f(n)=n^2 + 100n + 50 ∈ O(n^2).
Vakioita voidaan jättää: f(n)=3n ∈ O(n).
Summien ja tuotteiden käsittely: f(n)+h(n) ∈ O(max(g(n),q(n))) jos f∈O(g) ja h∈O(q). Jos algoritmi koostuu peräkkäisistä vaiheista, kompleksiteetit summautuvat (mutta asymptoottisesti dominoiva termi määrää luokan).
Nistetyt silmukat: jos sisäkkäisiä silmukoita ajetaan n kertaa kumpikin, tulos on O(n·n)=O(n^2).

Esimerkkikoodia ja analyysi

Yksinkertainen lineaarinen haku:

 for i in 1..n:     if A[i] == x:         return i

Tässä parhaassa tapauksessa (alkio löytyi heti) aika on O(1), pahimmassa tai odotusarvoisesti O(n).

Kaksi sisäkkäistä silmukkaa:

 for i in 1..n:     for j in 1..n:         do_constant_work()

Toiminto suoritetaan n·n kertaa, eli aikavaativuus on O(n^2).

Pahoin vs. keskimäärin ja parhain tapaus

Big O kuvaa ylärajaa (pahin tapaus tai asettelu) — se ei kerro, kuinka usein pahin tapaus toteutuu. On myös muita merkintöjä:

Θ (Theta) kuvaa tiukkaa rajaa (sekä ylä- että alaraja).
Ω (Omega) kuvaa alarajaa (parhain tai vähimmäisteho).

Kun kiinnostaa odotusarvoinen suorituskyky (keskiarvo), käytetään usein keskimääräistä analyysiä — se ei korvaa Big O -ylärajaa mutta antaa täsmentävää tietoa käytännöstä.

Tilavaativuus

Big O käytetään myös muistinkulutuksen arvioimiseen (tilavaativuus). Esimerkiksi algoritmi, joka tarvitsee lisämuistia vain muutaman muuttujan verran, on O(1) tilavaativuudeltaan, kun taas algoritmi joka varaa uuden taulukon koossa n on O(n).

Yhteenveto

Big O on kätevä tapa verrata algoritmeja riippumatta laitteistosta, koska se kuvaa kasvunopeutta asyymptoottisesti.
Se antaa ylärajan suoritusajalle (pahin tapaus) ja helpottaa algoritmien luokittelua.
Kun opit muutaman perussäännön (poista vakioita, jätä pienemmät termit, yhdistä monimutkaisuuksia), analysointi helpottuu merkittävästi.

Esimerkkejä

Seuraavissa esimerkeissä käytetään Python-kielellä kirjoitettua koodia. Huomaa, että tämä ei ole täydellinen luettelo Big O -tyypeistä.

Jatkuva

O ( 1 ) $O(1)$ kestää aina yhtä kauan syötteestä riippumatta. Otetaan esimerkiksi funktio, joka hyväksyy kokonaisluvun (nimeltään x) ja palauttaa sen arvon kaksinkertaisena:

def double(x): return x * 2 #Palauta arvo x kertaa 2.

Kun tämä funktio on hyväksynyt syötteen, se ottaa aina yhden askeleen palauttaakseen tulosteen. Se on vakio, koska se vie aina saman verran aikaa, joten se on O ( 1 ) . $O(1)$

Lineaarinen

O ( n ) {\displaystyle O(n)} $O(n)$ kasvaa syötteen koon mukaan, jota edustaa n {\displaystyle n} . Esimerkiksi seuraavassa funktiossa, joka hyväksyy n ja palauttaa kaikki luvut 1:stä n:ään:

def count(n): i = 1 #Luo laskuri nimeltä "i", jonka arvo on 1 while i <= n: #Kun i on pienempi tai yhtä suuri kuin n print(i) #Tulosta i:n arvo i = i + 1 #Määritä i uudelleen muotoon "arvo i + 1".

Jos syöttäisimme arvon 5, tulostuisi $1,2,3,4,5$ , jolloin tarvitaan 5 silmukkaa. Vastaavasti, jos syötämme arvon 100, tuloksena olisi $1,2,3...98,99,100$ , jolloin tarvitaan 100 silmukkaa. Jos syötteenä on n {\displaystyle n} , algoritmin suoritusaika on joka kerta tasan n {\displaystyle n} silmukkaa, joten se on O ( n ) {\displaystyle O(n)} . $O(n)$

Faktoriaali

O ( n ! ) $O(n!)$ kasvaa faktoriaalisesti, mikä tarkoittaa, että tarvittava aika kasvaa massiivisesti syötteen kasvaessa. Sanotaan esimerkiksi, että haluamme käydä viidessä kaupungissa ympäri maailmaa ja haluamme nähdä kaikki mahdolliset järjestykset (permutaatiot). Algoritmi, jonka voisimme kirjoittaa Pythonin itertools-kirjastoa käyttäen, on seuraava:

import itertools #Import itertools-kirjasto cities = ['London', 'Paris', 'Berlin', 'Amsterdam', 'Rome'] #Matriisi valitsemistamme kaupungeista def permutations(cities): #Keräämällä syötteenä joukko kaupunkeja: for i in itertools.permutations(cities): #Kunkin permutaation kohdalla (määritetään muuttujaan "i") print(i) #Tulos i.

Tämä algoritmi laskee jokaisen kaupunkiemme ainutlaatuisen permutaation ja antaa sen sitten tulosteen. Esimerkkejä tulosteista ovat:

('Lontoo', 'Pariisi', 'Berliini', 'Amsterdam', 'Rooma') ('Lontoo', 'Pariisi', 'Berliini', 'Rooma', 'Amsterdam') ('Lontoo', 'Pariisi', 'Amsterdam', 'Berliini', 'Rooma') ... ('Rooma', 'Amsterdam', 'Pariisi', 'Berliini', 'Berliini', 'Lontoo') ... ('Rooma', 'Amsterdam', 'Berliini', 'Berliini', 'Berliini', 'Lontoo', 'Rooma') ('Rooma', 'Amsterdam', 'Berliini', 'Berliini', 'Berliini', 'Berliini', 'Berliini', 'Berliini')

Tässä tapauksessa syöttöluettelomme on 5 kohdetta pitkä, ja jokaisella valinnalla jäljelle jäävät vaihtoehdot vähenevät yhdellä. Toisin sanoen 5 syötettä valitsee $5\times 4\times 3\times 2\times 1$ kohdetta (tai 5 ! {\displaystyle 5!} $5!$ ). Jos syötteemme on n {\displaystyle n} kaupunkia pitkä, tulosteiden lukumäärä on n ! {\displaystyle n!} $n!$ ; yleisesti ottaen, jos oletetaan, että käymme läpi jokaisen permutaation, tarvitsemme O ( n ! ) {\displaystyle O(n!)} $O(n!)$ silmukkaa sen suorittamiseen.

Little-o merkintätapa

Big-O-merkintätapaan liittyvä käsite on little-o-merkintätapa. Big-O:ta käytetään sanomaan, että funktio ei kasva nopeammin kuin toinen funktio, kun taas little-o:ta käytetään sanomaan, että funktio kasvaa hitaammin kuin toinen funktio. Jos kaksi funktiota kasvaa samaa vauhtia, voidaan käyttää big-O-merkintää, mutta little-o-merkintää ei. Ero big-O:n ja little-o:n välillä on samanlainen kuin ero ≤ {\displaystyle \leq } $\leq$ ja < {\displaystyle <} välillä. $<$

Jos f ( x ) {\displaystyle f(x)} kasvaa hitaammin kuin g ( x ) {\displaystyle g(x)} $g(x)$ , niin $f(x)\in O(g(x))$ ja $f(x)\in o(g(x))$ .
Jos f ( x ) {\displaystyle f(x)} kasvaa samaa vauhtia kuin g ( x ) {\displaystyle g(x)} $g(x)$ , niin $f(x)\in O(g(x))$ mutta f ( x ) ∉ $f(x)\not \in o(g(x))$ .
Jos f ( x ) {\displaystyle f(x)} kasvaa nopeammin kuin g ( x ) {\displaystyle g(x)} $g(x)$ , niin f ( x ) ∉ $f(x)\not \in O(g(x))$ ja f ( x ) ∉ $f(x)\not \in o(g(x))$ .

Kysymyksiä ja vastauksia

K: Mikä on Big O -merkintätapa?

V: Big O -notaatio on tapa verrata eri funktioiden kasvuvauhteja, ja sitä käytetään usein eri algoritmien tehokkuuden vertailuun laskemalla, kuinka paljon muistia ja aikaa se vie. Sitä voidaan käyttää myös ongelman monimutkaisuuden määrittämiseen.

K: Kuka käytti tätä merkintätapaa ensimmäisenä?

V: Matemaatikko Paul Bachmann (1837-1920) käytti tätä merkintätapaa ensimmäisenä kirjassaan "Analytische Zahlentheorie" vuonna 1896.

K: Mitä tarkoittaa iso O?

V: Iso O tarkoittaa "funktion järjestystä", joka viittaa funktioiden kasvunopeuteen.

K: Miten Big O:ta käytetään?

V: Big O -merkintää käytetään funktion kasvunopeuden ylärajan (suurimman mahdollisen määrän) löytämiseen, eli se laskee pisimmän ajan, joka kuluu syötteen muuttamiseen tulosteeksi. Tämä tarkoittaa, että algoritmit voidaan ryhmitellä sen mukaan, kuinka kauan ne vievät aikaa pahimmassa tapauksessa, jossa pisin reitti valitaan joka kerta.

K: Mitä ovat Landaun symbolit?

V: Landau-symbolit viittaavat Big O -merkintätapaan, joka on nimetty Edmund Landaun (1877-1938) mukaan, joka teki merkintätavan suosituksi.

K: Miksi Big O on hyödyllinen?

V: Big O:n avulla voimme mitata nopeutta ilman, että meidän tarvitsee ajaa ohjelmia tietokoneilla, koska se olettaa aina pahimman tapauksen skenaariot, mikä tekee siitä johdonmukaisen riippumatta tietokoneiden välisistä laitteistoeroista. Se osoittaa myös, kuinka tehokas algoritmi on ilman, että sitä tarvitsee ajaa tietokoneella.