Big O Notation forklaret med eksempler

Big O-notation er en måde at beskrive hastigheden eller kompleksiteten af ​​en given algoritme på. Hvis dit nuværende projekt kræver en foruddefineret algoritme, er det vigtigt at forstå, hvor hurtigt eller langsomt det er sammenlignet med andre muligheder.

Hvad er Big O notation, og hvordan fungerer det?

Kort sagt, Big O-notation fortæller dig antallet af operationer, som en algoritme vil foretage. Det får sit navn fra den bogstavelige "Big O" foran det estimerede antal operationer.

Hvad Big O-notation ikke fortæller dig, er algoritmens hastighed på få sekunder. Der er alt for mange faktorer, der påvirker den tid, det tager en algoritme at køre. I stedet bruger du Big O-notation til at sammenligne forskellige algoritmer efter antallet af operationer, de foretager.

Big O etablerer en worst-case kørselstid

Forestil dig, at du er lærer med en elev ved navn Jane. Du vil finde hendes optegnelser, så du bruger en simpel søgealgoritme til at gennemgå dit skoledistrikts database.

Du ved, at simpel søgning tager O (n) gange at køre. Dette betyder, at du i værste fald skal søge gennem hver enkelt post (repræsenteret af n) for at finde Jane's.

Men når du kører den enkle søgning, finder du ud af, at Jane's poster er den allerførste post i databasen. Du behøver ikke se på hver post - du fandt den ved dit første forsøg.

Tog denne algoritme O (n) tid? Eller tog det O (1) tid, fordi du fandt Janes optegnelser ved første forsøg?

I dette tilfælde er 0 (1) det bedste tilfælde - du var heldig, at Janes optegnelser var øverst. Men Big O-notation fokuserer på det værst tænkelige scenarie, som er 0 (n) til simpel søgning. Det er en forsikring om, at simpel søgning aldrig vil være langsommere end O (n) tid.

Algoritmens kørselstider vokser med forskellige hastigheder

Antag, at det tager 1 millisekund at kontrollere hvert element i skoledistriktets database.

Med simpel søgning, hvis du skal kontrollere 10 poster, tager det 10 ms at køre. Men med den binære søgealgoritme skal du kun kontrollere 3 elementer, hvilket tager 3 ms at køre.

I de fleste tilfælde vil den liste eller database, du skal søge, have hundreder eller tusinder af elementer.

Hvis der er 1 milliard elementer, vil brug af simpel søgning tage op til 1 milliard ms eller 11 dage. På den anden side tager brugen af ​​binær søgning kun 32 ms i værste fald:

Det er klart, at køretiderne til simpel søgning og binær søgning ikke vokser næsten med samme hastighed. Da listen over poster bliver større, tager binær søgning bare lidt mere tid at køre. Enkel søgningstid løber eksponentielt, efterhånden som listen over poster øges.

Derfor er det så vigtigt at vide, hvordan køretiden øges i forhold til en listestørrelse. Og det er her Big O-notationen er så nyttig.

Stor O-notation viser antallet af operationer

Som nævnt ovenfor viser Big O-notation ikke, hvornår en algoritme kører. I stedet viser det antallet af operationer, det vil udføre. Det fortæller dig, hvor hurtigt en algoritme vokser, og lader dig sammenligne den med andre.

Her er nogle almindelige algoritmer og deres løbetider i Big O-notation:

Stor O notation Eksempel på algoritme
O (log n) Binær søgning
På) Enkel søgning
O (n * log n) Quicksort
O (n2) Valg sortering
På!) Rejsende sælger

Nu ved du nok til at være farlig med Big O notation. Kom derude og begynd at sammenligne algoritmer.