streamalism.org

1. Oversikt

I denne opplæringen vil vi snakke om hva Big O Notation betyr. Vi vil gå gjennom noen eksempler for å undersøke effekten av koden din.

2. Intuisjonen av Big O Notation

Vi hører ofte ytelsen til en algoritme som er beskrevet ved hjelp av Big O Notation.

Studiet av ytelsen til algoritmer - eller algoritmisk kompleksitet - faller inn i algoritmeanalysefeltet. Algoritmeanalyse svarer på spørsmålet om hvor mange ressurser, for eksempel diskplass eller tid, en algoritme bruker.

Vi ser på tiden som en ressurs. Jo mindre tid en algoritme tar å fullføre, jo bedre er det vanligvis.

3. Konstant tidsalgoritmer - O (1)

Hvordan påvirker denne inngangsstørrelsen til en algoritme kjøretiden? Nøkkelen til å forstå Big O er å forstå hastighetene som ting kan vokse med. Satsen det er snakk om her er tid det tar per inngangsstørrelse.

Tenk på denne enkle koden:

int n = 1000; System.out.println ("Hei - din innspill er:" + n);

Det spiller tydeligvis ingen rolle hva n er over. Denne koden tar konstant tid å kjøre. Det er ikke avhengig av størrelsen på n.

På samme måte:

int n = 1000; System.out.println ("Hei - din innspill er:" + n); System.out.println ("Hmm .. Jeg gjør flere ting med:" + n); System.out.println ("Og mer:" + n);

Ovennevnte eksempel er også konstant tid. Selv om det tar 3 ganger så lang tid å løpe, det avhenger ikke av størrelsen på inngangen, n. Vi betegner konstant tidsalgoritmer som følger: O (1). Noter det O (2), O (3) eller O (1000) ville bety det samme.

Vi bryr oss ikke om nøyaktig hvor lang tid det tar å løpe, bare at det tar konstant tid.

4. Logaritmiske tidsalgoritmer - O (log n)

Konstant tidsalgoritmer er (asymptotisk) de raskeste. Logaritmisk tid er den nest raskeste. Dessverre er de litt vanskeligere å forestille seg.

Et vanlig eksempel på en logaritmisk tidsalgoritme er den binære søkealgoritmen. For å se hvordan du implementerer binært søk i Java, klikk her.

Det som er viktig her er at kjøretid vokser proporsjonalt med logaritmen til inngangen (i dette tilfellet logg til basen 2):

for (int i = 1; i <n; i = i * 2) {System.out.println ("Hei - jeg er opptatt av å se på:" + i); }

Hvis n er 8, vil utdataene være følgende:

Hei - Jeg er opptatt av å se på: 1 Hei - Jeg er opptatt med å se på: 2 Hei - Jeg er opptatt med å se på: 4

Vår enkle algoritme kjørte logg (8) = 3 ganger.

5. Lineære tidsalgoritmer - På)

Etter logaritmiske tidsalgoritmer får vi den neste raskeste klassen: lineære tidsalgoritmer.

Hvis vi sier at noe vokser lineært, mener vi at det vokser direkte proporsjonalt med størrelsen på inngangene.

Tenk på en enkel for løkke:

for (int i = 0; i <n; i ++) {System.out.println ("Hei - jeg er opptatt av å se på:" + i); }

Hvor mange ganger kjører dette for loop? n ganger, selvfølgelig! Vi vet ikke nøyaktig hvor lang tid det vil ta før dette løper - og vi bekymrer oss ikke for det.

Det vi vet er at den enkle algoritmen som er presentert ovenfor, vil vokse lineært med størrelsen på inngangen.

Vi foretrekker en kjøretid på 0,1n enn (1000n + 1000), men begge er fremdeles lineære algoritmer; de vokser begge direkte i forhold til størrelsen på deres innganger.

Igjen, hvis algoritmen ble endret til følgende:

for (int i = 0; i <n; i ++) {System.out.println ("Hei - jeg er opptatt av å se på:" + i); System.out.println ("Hmm .. La oss ta en titt på:" + i); System.out.println ("Og en annen:" + i); }

Kjøretiden vil fremdeles være lineær i størrelsen på inngangen, n. Vi betegner lineære algoritmer som følger: På).

Som med de konstante tidsalgoritmene, bryr vi oss ikke om spesifikasjonene for kjøretiden. O (2n + 1) er det samme som På), da Big O Notation handler om vekst for inngangsstørrelser.

6. N Log N Tidsalgoritmer - O (n log n)

n log n er neste klasse av algoritmer. Kjøretiden vokser proporsjonalt med n log n av inngangen:

for (int i = 1; i <= n; i ++) {for (int j = 1; j <n; j = j * 2) {System.out.println ("Hei - jeg er opptatt av å se på:" + i + "og" + j); }} 

For eksempel hvis n er 8, så kjører denne algoritmen 8 * logg (8) = 8 * 3 = 24 ganger. Enten vi har streng ulikhet eller ikke i for-sløyfen, er irrelevant av hensyn til en Big O-notasjon.

7. Algoritmer for polynomtid - O (np)

Neste gang har vi polynomiske tidsalgoritmer. Disse algoritmene er enda tregere enn n log n algoritmer.

Begrepet polynom er et generelt begrep som inneholder kvadratisk (n2), kubikk (n3), quartic (n4), etc. funksjoner. Det som er viktig å vite er at O (n2) er raskere enn O (n3) som er raskere enn O (n4), etc.

La oss ta en titt på et enkelt eksempel på en kvadratisk tidsalgoritme:

for (int i = 1; i <= n; i ++) {for (int j = 1; j <= n; j ++) {System.out.println ("Hei - jeg er opptatt av å se på:" + i + "og" + j); }} 

Denne algoritmen vil kjøre 82 = 64 ganger. Merk at hvis vi skulle hekke en annen for løkke, ville dette bli en O (n3) algoritme.

8. Eksponensielle tidsalgoritmer - O (kn)

Nå kommer vi inn i farlig territorium; disse algoritmene vokser proporsjonalt med noen faktor eksponentiert av inngangsstørrelsen.

For eksempel, O (2n) algoritmer dobles med hver ekstra inngang. Så hvis n = 2, disse algoritmene vil kjøre fire ganger; hvis n = 3, de vil kjøre åtte ganger (omtrent som det motsatte av logaritmiske tidsalgoritmer).

O (3n) algoritmer tredobles med hver ekstra inngang, O (kn) algoritmer vil bli k ganger større for hver ekstra inngang.

La oss ta en titt på et enkelt eksempel på en O (2n) tidsalgoritme:

for (int i = 1; i <= Math.pow (2, n); i ++) {System.out.println ("Hei - jeg er opptatt av å se på:" + i); }

Denne algoritmen vil kjøre 28 = 256 ganger.

9. Faktoriske tidsalgoritmer - På!)

I de fleste tilfeller er dette ganske så ille som det blir. Denne klassen av algoritmer har en kjøretid proporsjonal med faktoren for inngangsstørrelsen.

Et klassisk eksempel på dette er å løse det omreisende selgerproblemet ved å bruke en brute-force-tilnærming for å løse det.

En forklaring på løsningen på reisendeselgerproblemet ligger utenfor omfanget av denne artikkelen.

La oss i stedet se på en enkel På!) algoritme, som i forrige seksjoner:

for (int i = 1; i <= factorial (n); i ++) {System.out.println ("Hei - jeg er opptatt av å se på:" + i); }

hvor fabrikk (n) bare beregner n !. Hvis n er 8, vil denne algoritmen kjøre 8! = 40320 ganger.

10. Asymptotiske funksjoner

Big O er det som er kjent som en asymptotisk funksjon. Alt dette betyr at det handler om ytelsen til en algoritme på grensen - dvs. - når det kastes mye innspill.

Big O bryr seg ikke om hvor godt algoritmen din gjør med innganger av liten størrelse. Det er opptatt av store innganger (tenk å sortere en liste med en million tall vs. sortere en liste med 5 tall).

En annen ting å merke seg er at det er andre asymptotiske funksjoner. Big Θ (theta) og Big Ω (omega) beskriver også begge algoritmer på grensen (husk, grensen dette betyr bare for store innganger).

For å forstå forskjellene mellom disse tre viktige funksjonene, må vi først vite at hver av Big O, Big Θ og Big Ω beskriver en sett (dvs. en samling av elementer).

Her er medlemmene av settene våre algoritmer:

• Big O beskriver settet med alle algoritmer som kjører ikke verre enn en viss hastighet (det er en øvre grense)
• Omvendt beskriver Big Ω settet med alle algoritmer som kjører ikke bedre enn en viss hastighet (det er en nedre grense)
• Til slutt beskriver Big the settet med alle algoritmer som kjører på en viss hastighet (det er som likestilling)

Definisjonene vi har lagt ovenfor er ikke matematiske, men de vil hjelpe oss å forstå.

Vanligvis vil du høre ting beskrevet med Big O, men det gjør ikke vondt å vite om Big Θ og Big Ω.

11. Konklusjon

I denne artikkelen diskuterte vi Big O-notasjon, og hvordan å forstå kompleksiteten til en algoritme kan påvirke kjøretiden til koden din.

En flott visualisering av de forskjellige kompleksitetsklassene finner du her.

Som vanlig kan du finne kodebitene for denne opplæringen på GitHub.