Big O -merkintä - selitetään yksinkertaisesti kuvilla ja videolla

Kuva (ja suurin osa tässä artikkelissa) on kirjoittanut Adit Bhargava

Big O -merkintää käytetään kommunikoimaan kuinka nopea algoritmi on. Tämä voi olla tärkeä arvioitaessa muiden ihmisten algoritmeja ja arvioitaessa omia! Tässä artikkelissa selitän, mitä Big O -merkitys on, ja annan sinulle luettelon sitä käyttävien algoritmien yleisimmistä ajoajoista.

Algoritmin juoksuajat kasvavat eri nopeuksilla

Poikani selittää suuren O-merkinnän.

Poikallani Juudalla on paljon leluja. Itse asiassa hän on hankkinut miljardin lelua! Olet yllättynyt, kuinka nopeasti lapsi voi saada niin monta lelua, jos hän on ensimmäinen lapsenlapsensa perheen molemmilla puolilla.

Joka tapauksessa Juudalla on ongelma. Kun hänen ystävänsä vierailevat ja haluavat leikkiä tietyn lelun kanssa, lelun löytäminen voi kestää ENNEN. Joten hän haluaa luoda hakualgoritmin, joka auttaa häntä löytämään tietyn lelun mahdollisimman nopeasti. Hän yrittää päättää kahden erilaisen algoritmin välillä: yksinkertainen haku ja binaarinen haku. (Älä huolestu, jos et tunne näitä algoritmeja.)

Valitun algoritmin on oltava sekä nopea että oikea. Yhtäältä, binaarinen haku on nopeampaa. Ja Juudalla on usein vain noin 30 sekuntia ennen kuin hänen ystävänsä kyllästyy etsimään lelua. Toisaalta yksinkertaista hakualgoritmia on helpompi kirjoittaa, ja virheiden esiintymismahdollisuudet ovat pienemmät. Se olisi todella kiusallista, jos hänen ystävänsä löytäisi virheitä koodistaan! Ole erityisen varovainen, Juuda päättää ajastaa molemmat algoritmit luettelolla 100 lelua.

Oletetaan, että yhden lelun tarkistaminen vie 1 millisekunnin. Yksinkertaisella haulla Juudan on tarkistettava 100 lelua, joten haun suorittaminen kestää 100 ms. Toisaalta hänen on tarkistettava vain 7 lelua binaarisella haulla (log2 100 on suunnilleen 7, älä huoli, jos tämä matematiikka on hämmentävää, koska se ei ole tämän artikkelin pääkohta), joten haku vie 7 ms juosta. Mutta todella, luettelossa on miljardi lelua. Jos niin, kuinka kauan yksinkertainen haku vie? Kuinka kauan binaarinen haku kestää?

Kestoaika yksinkertaiseen hakuun verrattuna binaariseen hakuun luettelossa, jossa on 100 elementtiä

Juuda suorittaa binaarisen haun 1 miljardilla leluilla, ja se vie 30 ms (log2 1 000 000 000 on noin 30). ”32 ms!” Hän ajattelee. ”Binaarihaku on noin 15 kertaa nopeampi kuin yksinkertainen haku, koska yksinkertainen haku kesti 100 ms 100 elementtiä ja binaarihaku 7 ms. Joten yksinkertainen haku vie 30 × 15 = 450 ms, eikö niin? Alle 30 sekunnin kuluessa ystäväni kyllästyy. ”Juuda päättää mennä yksinkertaisella haulla. Onko se oikea valinta?

Ei. Osoittautuu, että Juuda oli väärässä ja menetti ystävänsä elämäksi. Yksinkertaisen haun ajoaika 1 miljardilla kohteella on miljardi ms, mikä on 11 päivää! Ongelmana on, että binaarisen haun ja yksinkertaisen haun ajoajat eivät kasva samalla nopeudella.

Juoksuajat kasvavat hyvin eri nopeuksilla! Kohteiden lukumäärän kasvaessa binaarinen haku vie hieman enemmän aikaa, mutta yksinkertainen haku vie paljon enemmän aikaa. Joten numeroiden luettelon kasvaessa, binaarinen haku tulee yhtäkkiä paljon nopeammaksi kuin yksinkertainen haku.

Joten Juuda oli väärässä, koska binaarinen haku oli aina 15 kertaa nopeampaa kuin yksinkertainen haku. Jos leluja on 1 miljardi, se on enemmän kuin 33 miljoonaa kertaa nopeampi.

On erittäin tärkeää tietää, kuinka juoksuaika kasvaa luettelon koon kasvaessa. Sieltä Big O -merkintä tulee.

Big O -merkintä kertoo kuinka nopea algoritmi on. Oletetaan esimerkiksi, että sinulla on luettelo koosta n. Yksinkertaisen haun on tarkistettava jokainen elementti, joten se vie n toimintaa. Suoritusaika Big O -merkinnässä on O (n).

Missä ovat sekunnit? Niitä ei ole - Big O ei kerro nopeutta sekunneissa. Big O -merkinnän avulla voit verrata toimintojen määrää. Se kertoo kuinka nopeasti algoritmi kasvaa.

Tehdään toinen esimerkki. Binaarihaku tarvitsee lokin n toiminnot tarkistaaksesi n-koon luettelon. Mikä on Big O -sovelluksen juoksuaika? Se on O (loki n). Yleensä Big O -merkintä kirjoitetaan seuraavasti.

Tämä kertoo operaatioiden lukumäärän, jonka algoritmi suorittaa. Sitä kutsutaan Big O -merkinnäksi, koska laitat “iso O” operaatioiden määrän eteen.

Big O vahvistaa pahimmassa tapauksessa ajon

Oletetaan, että käytät yksinkertaista hakua käyttäjän etsimiseen käyttäjän tietokannasta. Tiedät, että yksinkertaisen haun suorittaminen vie aikaa O (n), mikä tarkoittaa pahimmassa tapauksessa sinun on algoritmin tutkittava jokainen tietokannan käyttäjä. Tässä tapauksessa etsit käyttäjää nimellä 'aardvark213'. Tämä on luettelon ensimmäinen käyttäjä. Joten algoritmisi ei tarvinnut tarkastella kaikkia merkintöjä - se löysi sen ensimmäisestä yrityksestä. Oliko algoritmi O (n) -aikaa? Vai kestikö O (1) aikaa, koska se löysi henkilön ensimmäisestä yrityksestä?

Yksinkertainen haku vie vielä O (n) aikaa. Tässä tapauksessa algoritmi löysi etsimänsä heti. Se on paras tapaus. Mutta Big O -merkintä koskee pahinta tapausta. Joten voit sanoa, että pahimmassa tapauksessa algoritmin on tutkittava jokainen tietokannan käyttäjä kerran. Se on O (n) aika. Se on vakuutus - tiedät, että yksinkertainen haku ei koskaan ole hitaampaa kuin O (n) -aika.

Joitakin yleisiä Big O-ajoaikoja

Alkaen xkcd. Jos et saa vitsiä, oppi lisätietoja matkalle myyvästä myyjäongelmasta kurssillani Manning Publications -sivustolta. :)

Tässä on viisi Big O -aikaa, joita kohtaat paljon, lajiteltuina nopeimmasta hitaimpaan:

  • O (log n), tunnetaan myös nimellä log time. Esimerkki: Binaarihaku.
  • O (n), tunnetaan myös nimellä lineaarinen aika. Esimerkki: yksinkertainen haku.
  • O (n * log n). Esimerkki: Nopea lajittelualgoritmi, kuten pikavalinta.
  • O (n2). Esimerkki: Hidas lajittelualgoritmi, kuten valintalajittelu.
  • Päällä!). Esimerkki: Todella hidas algoritmi, kuten matkustava myyjä.

Visualisoidaan erilaiset Big O -ajat

Oletetaan, että piirrät 16 ruudun ruudukon, ja voit valita viidestä erilaisesta algoritmista. Jos käytät ensimmäistä algoritmia, ruudukon piirtäminen vie aikaa O (log n). Voit tehdä 10 toimenpidettä sekunnissa. Kun O (log n) -aikaa, vie 4 toimintoa 16 laatikon ruudukon piirtämiseksi (lokin 16 kanta 2 on 4). Joten ruudukon piirtäminen vie 0,4 sekuntia. Entä jos sinun on piirrettävä 1 024 laatikkoa? Loki 1 024 = 10 toimenpidettä tai 1 sekunti 1 024 laatikon ruudukon piirtämiseksi. Nämä numerot käyttävät ensimmäistä algoritmia.

Toinen algoritmi on hitaampi: se vie O (n) -aikaa. 16 laatikon piirtäminen vie 16 toimenpidettä ja 1 024 laatikon piirtäminen kestää 1 024 toimenpidettä. Kuinka paljon aikaa se on sekunneissa?

Tässä on, kuinka kauan ruudukon piirtäminen muille algoritmeille nopeimmasta hitaimpaan:

Myös muita ajoaikoja on, mutta nämä ovat viisi yleisintä.

Tämä on yksinkertaistaminen. Todellisuudessa et voi muuntaa Big O -ajasta lukuisiksi operaatioiksi tätä siististi, mutta tämä on hyvä arvio.

johtopäätös

Tässä ovat tärkeimmät noutot:

  • Algoritmin nopeutta ei mitata sekunnissa, vaan operaatioiden määrän kasvuna.
  • Sen sijaan puhumme siitä, kuinka nopeasti algoritmin ajoaika kasvaa sisääntulon koon kasvaessa.
  • Algoritmien ajoaika on ilmaistu Big O -merkinnällä.
  • O (log n) on nopeampi kuin O (n), mutta se muuttuu paljon nopeammin, kun etsimiesi kohteiden luettelo kasvaa.

Ja tässä on video, joka kattaa paljon mitä tässä artikkelissa on ja enemmän.

Toivon, että tämä artikkeli selitti sinulle enemmän Big O -merkintää. Tämä artikkeli perustuu Manning Publications -videokurssini, jonka nimi on Algorithms in Motion. Kurssi perustuu Adit Bhargavan hämmästyttävään kirjaan Grokking Algorithms. Hän piirsi kaikki tämän artikkelin hauskoja kuvia.

Jos opit parhaiten kirjojen kautta, hanki kirja! Jos opit parhaiten videoiden kautta, harkitse kurssin ostamista. Voit saada 39% kurssistani koodilla '39carnes'.