Big O Notation - Enkelt forklaret med illustrationer og video

Illustration (og mest i denne artikel) af Adit Bhargava

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

Algoritmens kørtider vokser med forskellige hastigheder

Min søn forklarer den store 'O' notation.

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.

Uanset hvad har Juda et problem. Når hans venner besøger og vil lege med et specifikt legetøj, kan det ALT tage at finde legetøjet. Så han vil oprette en søgealgoritme for at hjælpe ham med at finde et specifikt legetøj så hurtigt som muligt. Han prøver at bestemme mellem to forskellige søgealgoritmer: simpel søgning og binær søgning. (Bare rolig, hvis du ikke er bekendt 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 cirka 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 bugs introduceres. Det ville helt sikkert være pinligt, hvis hans ven fandt fejl i hans kode! For at være ekstra forsigtig beslutter Judah at time begge algoritmer med en liste med 100 legetøj.

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

Kørselstid for enkel søgning vs. 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 ca. 30). ”32 ms!” Tænker han. ”Binær søgning er cirka 15 gange hurtigere end simpel søgning, fordi enkel søgning tog 100 ms med 100 elementer, og binær søgning tog 7 ms. Så enkel søgning vil tage 30 × 15 = 450 ms, ikke? Vej 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 var forkert og mistede en ven for livet. Kørselstiden 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 takt.

Løbstider vokser med meget forskellige hastigheder! Efterhånden som antallet af genstande øger, tager binær søgning lidt mere tid at køre, men enkel søgning tager meget mere tid at køre. Efterhånden som listen over numre bliver større, bliver binær søgning pludselig meget hurtigere end simpel søgning.

Så Juda tog fejl af, 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 driftstiden ø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 f.eks., At du har en liste over størrelse n. Enkel søgning skal kontrollere hvert enkelt 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. Med stor O-notation kan du sammenligne antallet af operationer. Det fortæller dig, hvor hurtigt algoritmen vokser.

Lad os gøre et andet eksempel. Binær søgning har brug for log 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 skrives Big O-notation som følger.

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

Big O fastlægger en worst-case køretid

Antag, at du bruger 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 i værste tilfælde betyder, at du er algoritme nødt til at kigge 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 den fandt personen på første forsøg?

Enkel søgning tager stadig O (n) tid. I dette tilfælde fandt algoritmen, hvad den søgte øjeblikkeligt. 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 kigge gennem enhver 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

Fra xkcd. Hvis du ikke får vittigheden, kan du lære mere om det rejsende sælgerproblem på mit kursus fra Manning Publications. :)

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: Simpel søgning.
  • O (n * log n). Eksempel: En hurtig sorteringsalgoritme, som quicksort.
  • O (n2). Eksempel: En langsom sorteringsalgoritme, som f.eks. Valgssortering.
  • På!). Eksempel: En virkelig langsom algoritme, som den rejsende sælger.

Visualisering af forskellige Big O-kørtider

Antag, at du tegner et gitter med 16 kasser, og du kan vælge mellem 5 forskellige algoritmer for 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 vil det tage 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 gitteret. Hvad hvis du skal tegne 1.024 kasser? Det tager dig log 1.024 = 10 operationer, eller 1 sekund for at tegne et gitter på 1.024 kasser. Disse numre bruger den første algoritme.

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

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

Der er også andre kørtider, men dette er de fem mest almindelige.

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

Konklusion

Her er de vigtigste afhentningssteder:

  • Algoritmehastighed måles ikke i sekunder, men i vækst i antallet af operationer.
  • I stedet snakker vi om, hvor hurtigt køretiden for en algoritme øges, når størrelsen på input øges.
  • Køretid 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 bragte 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. Han er den, der tegnet 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'.