streamalism.org

1. Oversigt

I denne vejledning vil vi tale om hvad Big O Notation betyder. Vi gennemgår et par eksempler for at undersøge dens virkning på din kodes kørselstid.

2. Intuitionen med Big O Notation

Vi hører ofte ydeevne for en algoritme, der er beskrevet ved hjælp af Big O Notation.

Undersøgelsen af ​​udførelsen af ​​algoritmer - eller algoritmisk kompleksitet - falder inden for algoritmeanalyse. Algoritmeanalyse svarer på spørgsmålet om, hvor mange ressourcer, såsom diskplads eller tid, en algoritme bruger.

Vi ser på tiden som en ressource. Jo mindre tid en algoritme tager at gennemføre, jo bedre er det typisk.

3. Konstant tidsalgoritmer - O (1)

Hvordan påvirker denne inputstørrelse af en algoritme dens driftstid? Nøglen til forståelse af Big O er forståelse af de hastigheder, hvormed ting kan vokse. Den sats, der er tale om her, er tid taget pr. inputstørrelse.

Overvej dette enkle stykke kode:

int n = 1000; System.out.println ("Hej - dit input er:" + n);

Det betyder klart, at det ikke betyder noget n er ovenfor. Dette stykke kode tager konstant tid at køre. Det afhænger ikke af størrelsen på n.

Tilsvarende:

int n = 1000; System.out.println ("Hej - dit input er:" + n); System.out.println ("Hmm .. Jeg laver flere ting med:" + n); System.out.println ("Og mere:" + n);

Ovenstående eksempel er også konstant tid. Selvom det tager 3 gange så lang tid at løbe, det afhænger ikke af størrelsen på input, n. Vi betegner konstant tidsalgoritmer som følger: O (1). Noter det O (2), O (3) eller endda O (1000) ville betyde det samme.

Vi er ligeglad med nøjagtigt, hvor lang tid det tager at løbe, kun at det tager konstant tid.

4. Logaritmiske tidsalgoritmer - O (log n)

Konstant tidsalgoritmer er (asymptotisk) de hurtigste. Logaritmisk tid er den næste hurtigste. Desværre er de lidt sværere at forestille sig.

Et almindeligt eksempel på en logaritmisk tidsalgoritme er den binære søgealgoritme. Klik her for at se, hvordan binær søgning implementeres i Java.

Hvad der er vigtigt her er, at løbstid vokser i forhold til logaritmen til input (i dette tilfælde logger du til base 2):

for (int i = 1; i <n; i = i * 2) {System.out.println ("Hej - jeg har travlt med at se på:" + i); }

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

Hej - Jeg har travlt med at se på: 1 Hej - Jeg har travlt med at se på: 2 Hej - Jeg har travlt med at se på: 4

Vores enkle algoritme kørte log (8) = 3 gange.

5. Lineære tidsalgoritmer - På)

Efter logaritmiske tidsalgoritmer får vi den næste hurtigste klasse: lineære tidsalgoritmer.

Hvis vi siger, at noget vokser lineært, mener vi, at det vokser direkte proportionalt med størrelsen på dets input.

Tænk på en enkel til løkke:

for (int i = 0; i <n; i ++) {System.out.println ("Hej - jeg har travlt med at se på:" + i); }

Hvor mange gange kører dette til loop? n gange, selvfølgelig! Vi ved ikke nøjagtigt, hvor lang tid det tager, før dette kører - og det bekymrer vi os ikke om.

Hvad vi ved er, at den enkle algoritme, der er præsenteret ovenfor, vokser lineært med størrelsen på dens input.

Vi foretrækker en løbetid på 0,1 n end (1000n + 1000), men begge er stadig lineære algoritmer; de vokser begge direkte i forhold til størrelsen på deres input.

Igen, hvis algoritmen blev ændret til følgende:

for (int i = 0; i <n; i ++) {System.out.println ("Hej - jeg har travlt med at se på:" + i); System.out.println ("Hmm .. Lad os se igen på:" + i); System.out.println ("Og en anden:" + i); }

Runtiden vil stadig være lineær i størrelsen af ​​dens input, n. Vi betegner lineære algoritmer som følger: På).

Som med de konstante tidsalgoritmer er vi ligeglade med køretidens detaljer. O (2n + 1) er det samme som På), da Big O Notation vedrører vækst for inputstørrelser.

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

n log n er den næste klasse af algoritmer. Løbetiden vokser i forhold til n log n af input:

for (int i = 1; i <= n; i ++) {for (int j = 1; j <n; j = j * 2) {System.out.println ("Hej - jeg har travlt med at se på:" + i + "og" + j); }} 

For eksempel, hvis n er 8, så kører denne algoritme 8 * log (8) = 8 * 3 = 24 gange. Uanset om vi har streng ulighed eller ej i for-sløjfen, er det irrelevant af hensyn til en Big O-notation.

7. Algoritmer til polynomer - O (np)

Næste gang har vi polynomiske tidsalgoritmer. Disse algoritmer er endnu langsommere end n log n algoritmer.

Udtrykket polynom er et generelt udtryk, der indeholder kvadratisk (n2), kubisk (n3), kvartisk (n4)osv. funktioner. Hvad der er vigtigt at vide er det O (n2) er hurtigere end O (n3) hvilket er hurtigere end O (n4), etc.

Lad os se på et simpelt eksempel på en kvadratisk tidsalgoritme:

for (int i = 1; i <= n; i ++) {for (int j = 1; j <= n; j ++) {System.out.println ("Hej - jeg har travlt med at se på:" + i + "og" + j); }} 

Denne algoritme kører 82 = 64 gange. Bemærk, hvis vi skulle rede en anden til løkke, ville dette blive en O (n3) algoritme.

8. Eksponentielle tidsalgoritmer - O (kn)

Nu kommer vi ind i farligt område; disse algoritmer vokser i forhold til en eller anden faktor eksponeret af inputstørrelsen.

For eksempel, O (2n) algoritmer fordobles med hvert ekstra input. Så hvis n = 2, disse algoritmer kører fire gange; hvis n = 3, de kører otte gange (som det modsatte af logaritmiske tidsalgoritmer).

O (3n) algoritmer tredobles med hvert ekstra input, O (kn) algoritmer bliver k gange større med hvert ekstra input.

Lad os se på et simpelt eksempel på en O (2n) tidsalgoritme:

for (int i = 1; i <= Math.pow (2, n); i ++) {System.out.println ("Hej - jeg har travlt med at se på:" + i); }

Denne algoritme kører 28 = 256 gange.

9. Faktoriske tidsalgoritmer - På!)

I de fleste tilfælde er dette stort set så slemt som det bliver. Denne klasse af algoritmer har en kørselstid, der er proportional med faktorens inputstørrelse.

Et klassisk eksempel på dette er at løse det rejsende sælgerproblem ved hjælp af en brute-force tilgang til at løse det.

En forklaring på løsningen på problemet med den rejsende sælger ligger uden for anvendelsesområdet for denne artikel.

Lad os i stedet se på en simpel På!) algoritme, som i de foregående afsnit:

for (int i = 1; i <= factorial (n); i ++) {System.out.println ("Hey - jeg har travlt med at se på:" + i); }

hvor fabrik (n) bare beregner n !. Hvis n er 8, kører denne algoritme 8! = 40320 gange.

10. Asymptotiske funktioner

Big O er det, der er kendt som en asymptotisk funktion. Alt dette betyder, at det vedrører udførelsen af ​​en algoritme ved grænsen - dvs. - når der kastes masser af input.

Big O er ligeglad med, hvor godt din algoritme klarer sig med input af lille størrelse. Det er bekymret med store input (tænk at sortere en liste med en million tal vs. sortere en liste på 5 numre).

En anden ting at bemærke er, at der er andre asymptotiske funktioner. Big Θ (theta) og Big Ω (omega) beskriver begge begge algoritmer ved grænsen (husk, grænsen dette betyder bare for store input).

For at forstå forskellene mellem disse 3 vigtige funktioner skal vi først vide, at hver af Big O, Big Θ og Big Ω beskriver en sæt (dvs. en samling af elementer).

Her er medlemmerne af vores sæt algoritmer selv:

• Big O beskriver sættet med alle algoritmer, der kører ikke værre end en bestemt hastighed (det er en øvre grænse)
• Omvendt beskriver Big Ω sættet med alle algoritmer, der kører ikke bedre end en bestemt hastighed (det er en lavere grænse)
• Endelig beskriver Big the sættet med alle algoritmer, der kører på en bestemt hastighed (det er som ligestilling)

De definitioner, vi har sat ovenfor, er ikke matematiske nøjagtige, men de vil hjælpe vores forståelse.

Normalt vil du høre ting beskrevet ved hjælp af Big O, men det gør ikke ondt at vide om Big Θ og Big Ω.

11. Konklusion

I denne artikel diskuterede vi Big O-notation, og hvordan at forstå kompleksiteten af ​​en algoritme kan påvirke kodenes kørselstid.

En stor visualisering af de forskellige kompleksitetsklasser kan findes her.

Som sædvanligt kan kodestykkerne til denne vejledning findes på GitHub.