Big O Notation - Simpel forklaret med illustrationer og video

Big O-notation bruges til at kommunikere, hvor hurtig en algoritme er. Dette kan være vigtigt, når du vurderer andres algoritmer, og når du vurderer dine egne! I denne artikel forklarer jeg, hvad Big O-notation er, og giver dig en liste over de mest almindelige køretider for algoritmer, der bruger den.

Algoritmens kørselstider vokser med forskellige hastigheder

Min søn Juda har en masse legetøj. Faktisk har han erhvervet en milliard legetøj! Du vil blive overrasket over, hvor hurtigt et barn kan få så mange legetøj, hvis han er det første barnebarn på begge sider af familien. ??

Under alle omstændigheder har Juda et problem. Når hans venner besøger og vil lege med et specifikt legetøj, kan det tage ALDRIG at finde legetøjet. Så han ønsker at oprette en søgealgoritme for at hjælpe ham med at finde et specifikt legetøj så hurtigt som muligt. Han prøver at vælge mellem to forskellige søgealgoritmer: enkel søgning og binær søgning. (Bare rolig, hvis du ikke er fortrolig med disse algoritmer.)

Den valgte algoritme skal være både hurtig og korrekt. På den ene side er binær søgning hurtigere. Og Juda har ofte kun ca. 30 sekunder, før hans ven keder sig på udkig efter et legetøj. På den anden side er en simpel søgealgoritme lettere at skrive, og der er mindre chance for, at der introduceres bugs. Det ville helt sikkert være pinligt, hvis hans ven fandt fejl i sin kode! For at være ekstra forsigtig beslutter Judah at time begge algoritmer med en liste over 100 legetøj.

Lad os antage, at det tager 1 millisekund at kontrollere et legetøj. Med simpel søgning skal Juda kontrollere 100 legetøj, så søgningen tager 100 ms at køre. På den anden side skal han kun kontrollere 7 legetøj med binær søgning (log2 100 er cirka 7, skal du ikke bekymre dig, hvis denne matematik er forvirrende, da det ikke er hovedpunktet i denne artikel), så søgning tager 7 ms at løbe. Men virkelig, listen vil have en milliard legetøj. Hvis det gør det, hvor lang tid tager simpel søgning? Hvor lang tid tager binær søgning?

Kørselstid til simpel søgning versus binær søgning med en liste over 100 elementer

Judah kører binær søgning med 1 milliard legetøj, og det tager 30 ms (log2 1.000.000.000 er cirka 30). “32 ms!” han tænker. ”Binær søgning er cirka 15 gange hurtigere end simpel søgning, fordi simpel søgning tog 100 ms med 100 elementer, og binær søgning tog 7 ms. Så enkel søgning tager 30 × 15 = 450 ms, ikke? Langt under de 30 sekunder, det tager for min ven at kede sig. ” Juda beslutter at gå med simpel søgning. Er det det rigtige valg?

Nej. Det viser sig, at Juda tog fejl og mistede en ven for livet. ? Løbetiden for enkel søgning med 1 milliard varer vil være 1 milliard ms, hvilket er 11 dage! Problemet er, at køretiderne for binær søgning og simpel søgning ikke vokser i samme hastighed.

Kørselstider vokser med meget forskellige hastigheder! Efterhånden som antallet af varer stiger, tager binær søgning lidt mere tid at køre, men simpel søgning tager meget mere tid at køre. Så når listen over tal bliver større, bliver binær søgning pludselig meget hurtigere end simpel søgning.

Så Juda tog fejl ved, at binær søgning altid var 15 gange hurtigere end simpel søgning. Hvis der er 1 milliard legetøj, er det mere som 33 millioner gange hurtigere.

Det er meget vigtigt at vide, hvordan kørselstiden øges, når listestørrelsen øges. Det er her Big O notation kommer ind.

Big O-notation fortæller dig, hvor hurtig en algoritme er. Antag for eksempel, at du har en liste over størrelse n . Enkel søgning skal kontrollere hvert element, så det tager n operationer. Kørselstiden i Big O-notation er O ( n ).

Hvor er sekunderne? Der er ingen - Big O fortæller dig ikke hastigheden på få sekunder. Big O-notation giver dig mulighed for at sammenligne antallet af operationer. Det fortæller dig, hvor hurtigt algoritmen vokser.

Lad os gøre et andet eksempel. Binær søgning skal logge n operationer for at kontrollere en liste over størrelse n . Hvad er køretiden i Big O notation? Det er O (log n ). Generelt er Big O-notation skrevet som følger.

Dette fortæller dig antallet af operationer, som en algoritme foretager. Det kaldes Big O-notation, fordi du sætter en "stor O" foran antallet af operationer.

Big O etablerer en worst-case kørselstid

Antag at du bruger en simpel søgning til at lede efter en bruger i din brugerdatabase. Du ved, at simpel søgning tager O ( n ) tid at køre, hvilket betyder i værste fald, at din algoritme bliver nødt til at se igennem alle brugere i databasen. I dette tilfælde leder du efter en bruger med navnet 'aardvark213'. Dette er den første bruger på listen. Så din algoritme behøvede ikke at se på hver post - den fandt den ved første forsøg. Tog algoritmen O ( n ) tid? Eller tog det O (1) tid, fordi det fandt personen ved første forsøg?

Enkel søgning tager stadig O ( n ) tid. I dette tilfælde fandt algoritmen det, den søgte med det samme. Det er det bedste tilfælde. Men Big O-notation handler om det værste tilfælde . Så du kan sige , at algoritmen i værste fald skal gennemse hver bruger i databasen en gang. Det er O ( n ) tid. Det er en forsikring - du ved, at simpel søgning aldrig vil være langsommere end O ( n ) tid.

Nogle almindelige Big O-løbetider

Her er fem store O-løbetider, som du vil støde på meget, sorteret fra hurtigste til langsomste:

  • O (log n ), også kendt som logtid. Eksempel: Binær søgning.
  • O ( n ), også kendt som lineær tid . Eksempel: Enkel søgning.
  • O ( n * log n ). Eksempel: En hurtig sorteringsalgoritme, som quicksort.
  • O ( n 2). Eksempel: En langsom sorteringsalgoritme, som valgsortering.
  • O ( n !). Eksempel: En rigtig langsom algoritme, som den rejsende sælger.

Visualisering af forskellige Big O-løbetider

Antag at du tegner et gitter med 16 kasser, og du kan vælge mellem 5 forskellige algoritmer til at gøre det. Hvis du bruger den første algoritme, vil det tage dig O (log n ) tid at tegne gitteret. Du kan udføre 10 operationer pr. Sekund. Med O (log n ) -tid tager det dig 4 operationer at tegne et gitter med 16 kasser (log 16 base 2 er 4). Så det tager dig 0,4 sekunder at tegne nettet. Hvad hvis du skal tegne 1.024 kasser? Det tager dig at logge 1.024 = 10 operationer eller 1 sekund at tegne et gitter med 1.024 kasser. Disse tal bruger den første algoritme.

Den anden algoritme er langsommere: det tager O ( n ) tid. Det tager 16 operationer at tegne 16 kasser, og det tager 1.024 operationer at tegne 1.024 kasser. Hvor meget tid er det i sekunder?

Her er hvor lang tid det vil tage at tegne et gitter for resten af ​​algoritmerne, fra hurtigste til langsomste:

Der er også andre løbetider, men disse er de fem mest almindelige.

Dette er en forenkling. I virkeligheden kan du ikke konvertere fra en Big O-kørselstid til en række operationer dette pænt, men dette er et godt skøn.

Konklusion

Her er de vigtigste takeaways:

  • Algoritmehastighed måles ikke i sekunder, men i vækst af antallet af operationer.
  • I stedet for taler vi om, hvor hurtigt en algoritmes driftstid øges, når inputstørrelsen øges.
  • Løbetid for algoritmer udtrykkes i Big O-notation.
  • O (log n ) er hurtigere end O ( n ), men det bliver meget hurtigere, når listen over varer, du søger, vokser.

Og her er en video, der dækker meget af, hvad der er i denne artikel og mere.

Jeg håber, at denne artikel gav dig mere klarhed om Big O-notation. Denne artikel er baseret på en lektion i mit videokursus fra Manning Publications kaldet Algorithms in Motion. Kurset er baseret på den fantastiske bog Grokking Algorithms af Adit Bhargava. Det er ham, der tegner alle de sjove illustrationer i denne artikel.

Hvis du lærer bedst gennem bøger, skal du hente bogen! Hvis du lærer bedst gennem videoer, kan du overveje at købe mit kursus. Du kan få 39% rabat på mit kursus ved at bruge koden ' 39carnes '.