Asymptoottinen suoritusaika | tapa verrata eri funktioiden kasvunopeuksia

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.

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.