Big O Analysis er en teknik til at analysere og rangordne effektiviteten af algoritmer.
Dette giver dig mulighed for at vælge de mest effektive og skalerbare algoritmer. Denne artikel er et Big O Cheat Sheet, der forklarer alt hvad du behøver at vide om Big O Notation.
Indholdsfortegnelse
Hvad er Big O-analyse?
Big O Analysis er en teknik til at analysere, hvor godt algoritmer skalerer. Konkret spørger vi, hvor effektiv en algoritme er, når inputstørrelsen øges.
Effektivitet er, hvor godt systemressourcer bruges, mens der produceres et output. De ressourcer, vi primært er optaget af, er tid og hukommelse.
Derfor, når vi udfører Big O-analyse, er de spørgsmål, vi stiller:
Svaret på det første spørgsmål er algoritmens rumkompleksitet, mens svaret på det andet er dens tidskompleksitet. Vi bruger en speciel notation kaldet Big O Notation til at udtrykke svar på begge spørgsmål. Dette vil blive dækket næste gang i Big O Cheat Sheet.
Forudsætninger
Før jeg går videre, må jeg sige, at for at få mest muligt ud af dette Big O Cheat Sheet, skal du forstå lidt algebra. Derudover, fordi jeg vil give Python-eksempler, er det også nyttigt at forstå lidt af Python. En dybdegående forståelse er unødvendig, da du ikke vil skrive nogen kode.
Sådan udføres Big O-analyse
I dette afsnit vil vi dække, hvordan man udfører Big O-analyse.
Når du udfører Big O Complexity Analysis, er det vigtigt at huske, at algoritmens ydeevne afhænger af, hvordan inputdata er struktureret.
For eksempel kører sorteringsalgoritmer hurtigst, når dataene på listen allerede er sorteret i den rigtige rækkefølge. Det er det bedste scenario for algoritmens ydeevne. På den anden side er de samme sorteringsalgoritmer langsomst, når data er struktureret i omvendt rækkefølge. Det er det værste scenario.
Når vi udfører Big O-analyse, tager vi kun hensyn til det værst tænkelige scenarie.
Rumkompleksitetsanalyse
Lad os begynde dette Big O Cheat Sheet med at dække, hvordan man udfører rumkompleksitetsanalyse. Vi ønsker at overveje, hvordan den ekstra hukommelse en algoritme bruger skalerer, efterhånden som inputtet bliver større og større.
For eksempel bruger funktionen nedenfor rekursion til at sløjfe fra n til nul. Det har en rumkompleksitet, der er direkte proportional med n. Dette skyldes, at når n vokser, stiger antallet af funktionskald på opkaldsstakken også. Så det har en rumkompleksitet på O(n).
def loop_recursively(n):
if n == -1:
return
else:
print(n)
loop_recursively(n - 1)
En bedre implementering ville dog se sådan ud:
def loop_normally(n):
count = n
while count >= 0:
print(count)
count =- 1
I algoritmen ovenfor opretter vi kun én ekstra variabel og bruger den til at loope. Hvis n blev større og større, ville vi stadig kun bruge én ekstra variabel. Derfor har algoritmen konstant rumkompleksitet, betegnet med “O(1)”-symbolet.
Ved at sammenligne rumkompleksiteten af de to algoritmer ovenfor konkluderede vi, at while-løkken var mere effektiv end rekursion. Det er hovedformålet med Big O Analysis: at analysere, hvordan algoritmer ændrer sig, når vi kører dem med større input.
Tidskompleksitetsanalyse
Når vi udfører tidskompleksitetsanalyse, er vi ikke bekymrede over væksten i den samlede tid, som algoritmen tager. Vi er snarere bekymrede over væksten i beregningsmæssige skridt. Dette skyldes, at den faktiske tid afhænger af mange systemiske og tilfældige faktorer, som er svære at tage højde for. Så vi sporer kun væksten af beregningstrin og antager, at hvert trin er ens.
Overvej følgende eksempel for at demonstrere tidskompleksitetsanalyse:
Antag, at vi har en liste over brugere, hvor hver bruger har et ID og navn. Vores opgave er at implementere en funktion, der returnerer brugerens navn, når der gives et ID. Sådan kan vi gøre det:
users = [
{'id': 0, 'name': 'Alice'},
{'id': 1, 'name': 'Bob'},
{'id': 2, 'name': 'Charlie'},
]
def get_username(id, users):
for user in users:
if user['id'] == id:
return user['name']
return 'User not found'
get_username(1, users)
Med en liste over brugere gennemgår vores algoritme hele brugerens array for at finde brugeren med det korrekte ID. Når vi har 3 brugere, udfører algoritmen 3 iterationer. Når vi har 10, udfører den 10.
Derfor er antallet af trin lineært og direkte proportionalt med antallet af brugere. Så vores algoritme har lineær tidskompleksitet. Vi kan dog forbedre vores algoritme.
Antag, at vi i stedet for at gemme brugere på en liste, gemte dem i en ordbog. Så vil vores algoritme til at slå en bruger op se sådan ud:
users = {
'0': 'Alice',
'1': 'Bob',
'2': 'Charlie'
}
def get_username(id, users):
if id in users:
return users[id]
else:
return 'User not found'
get_username(1, users)
Antag med denne nye algoritme, at vi havde 3 brugere i vores ordbog; vi ville udføre flere trin for at få brugernavnet. Og antag, at vi havde flere brugere, f.eks. ti. Vi ville udføre det samme antal trin som før for at få brugeren. Efterhånden som antallet af brugere vokser, forbliver antallet af trin for at få et brugernavn konstant.
Derfor har denne nye algoritme konstant kompleksitet. Det er lige meget, hvor mange brugere vi har; antallet af taget beregningstrin er det samme.
Hvad er Big O-notation?
I det foregående afsnit diskuterede vi, hvordan man beregner Big O-rum- og tidskompleksiteten for forskellige algoritmer. Vi brugte ord som lineær og konstant til at beskrive kompleksiteter. En anden måde at beskrive kompleksitet på er at bruge Big O Notation.
Big O Notation er en måde at repræsentere en algoritmes rum- eller tidskompleksiteter. Notationen er forholdsvis enkel; det er et O efterfulgt af parenteser. Inden for parentesen skriver vi en funktion af n for at repræsentere den særlige kompleksitet.
Lineær kompleksitet er repræsenteret af n, så vi ville skrive det som O(n) (læses som “O af n”). Konstant kompleksitet er repræsenteret ved 1, så vi ville skrive det som O(1).
Der er flere kompleksiteter, som vi vil diskutere i næste afsnit. Men generelt skal du følge følgende trin for at skrive en algoritmes kompleksitet:
Resultatet af det bliver det udtryk, vi bruger i vores parentes.
Eksempel:
Overvej følgende Python-funktion:
users = [
'Alice',
'Bob',
'Charlie'
]
def print_users(users):
number_of_users = len(users)
print("Total number of users:", number_of_users)
for i in number_of_users:
print(i, end=': ')
print(user)
Nu vil vi beregne algoritmens Big O Time-kompleksitet.
Vi skriver først en matematisk funktion af nf(n) for at repræsentere antallet af beregningstrin algoritmen tager. Husk at n repræsenterer inputstørrelsen.
Fra vores kode udfører funktionen to trin: et til at beregne antallet af brugere og det andet til at udskrive antallet af brugere. Derefter udfører den for hver bruger to trin: et til at udskrive indekset og et til at udskrive brugeren.
Derfor kan den funktion, der bedst repræsenterer antallet af taget beregningstrin, skrives som f(n) = 2 + 2n. Hvor n er antallet af brugere.
Går vi videre til trin to, vælger vi det mest dominerende udtryk. 2n er et lineært led, og 2 er et konstant led. Lineær er mere dominant end konstant, så vi vælger 2n, det lineære led.
Så vores funktion er nu f(n) = 2n.
Det sidste trin er at eliminere koefficienter. I vores funktion har vi 2 som vores koefficient. Så vi fjerner det. Og funktionen bliver f(n) = n. Det er det udtryk, vi bruger mellem vores parentes.
Derfor er tidskompleksiteten af vores algoritme O(n) eller lineær kompleksitet.
Forskellige Big O-kompleksiteter
Det sidste afsnit i vores Big O Cheat Sheet vil vise dig forskellige kompleksiteter og de tilhørende grafer.
#1. Konstant
Konstant kompleksitet betyder, at algoritmen bruger en konstant mængde plads (når der udføres rumkompleksitetsanalyse) eller et konstant antal trin (når der udføres tidskompleksitetsanalyse). Dette er den mest optimale kompleksitet, da algoritmen ikke behøver yderligere plads eller tid, efterhånden som inputtet vokser. Den er derfor meget skalerbar.
Konstant kompleksitet er repræsenteret som O(1). Det er dog ikke altid muligt at skrive algoritmer, der kører i konstant kompleksitet.
#2. Logaritmisk
Logaritmisk kompleksitet er repræsenteret ved udtrykket O(log n). Det er vigtigt at bemærke, at hvis logaritmebasen ikke er angivet i Datalogi, antager vi, at den er 2.
Derfor er log n log2n. Logaritmiske funktioner er kendt for at vokse hurtigt i starten og derefter bremse. Det betyder, at de skalerer og arbejder effektivt med et stadig større antal n.
#3. Lineær
For lineære funktioner, hvis den uafhængige variabel skaleres med en faktor på p. Den afhængige variabel skaleres med den samme faktor p.
Derfor vokser en funktion med en lineær kompleksitet med samme faktor som inputstørrelsen. Hvis inputstørrelsen fordobles, vil antallet af beregningstrin eller hukommelsesforbrug også blive det. Lineær kompleksitet er repræsenteret ved symbolet O(n).
#4. Linearitmisk
O (n * log n) repræsenterer linearitmiske funktioner. Linearitmiske funktioner er en lineær funktion ganget med logaritmefunktionen. Derfor giver en linearitmisk funktion resultater, der er lidt større end lineære funktioner, når log n er større end 1. Dette skyldes, at n stiger, når de ganges med et tal større end 1.
Log n er større end 1 for alle værdier af n større end 2 (husk, log n er log2n). Derfor, for enhver værdi på n større end 2, er linearitmiske funktioner mindre skalerbare end lineære funktioner. Hvoraf n er større end 2 i de fleste tilfælde. Så linearitmiske funktioner er generelt mindre skalerbare end logaritmiske funktioner.
#5. Kvadratisk
Kvadratisk kompleksitet er repræsenteret ved O(n2). Det betyder, at hvis din inputstørrelse øges med 10 gange, øges antallet af trin, der tages eller plads, der bruges med 102 gange eller 100! Dette er ikke særlig skalerbart, og som du kan se på grafen, blæser kompleksiteten meget hurtigt op.
Kvadratisk kompleksitet opstår i algoritmer, hvor du sløjfer n gange, og for hver iteration sløjfer du n gange igen, for eksempel i Bubble Sort. Selvom det generelt ikke er ideelt, har du til tider ingen anden mulighed end at implementere algoritmer med kvadratisk kompleksitet.
#6. Polynomium
En algoritme med polynomisk kompleksitet er repræsenteret ved O(np), hvor p er et konstant heltal. P repræsenterer rækkefølgen, hvori n er hævet.
Denne kompleksitet opstår, når du har et antal indlejrede sløjfer. Forskellen mellem polynomiel kompleksitet og kvadratisk kompleksitet er kvadratisk er i størrelsesordenen 2, mens polynomiet har et hvilket som helst tal større end 2.
#7. Eksponentiel
Eksponentiel kompleksitet vokser endnu hurtigere end polynomisk kompleksitet. I matematik er standardværdien for eksponentialfunktionen konstanten e (Eulers tal). I datalogi er standardværdien for den eksponentielle funktion imidlertid 2.
Eksponentiel kompleksitet er repræsenteret ved symbolet O(2n). Når n er 0, er 2n 1. Men når n øges til 5, blæser 2n op til 32. En stigning i n med én vil fordoble det foregående tal. Derfor er funktioner af eksponentiel ikke særlig skalerbare.
#8. Faktoriel
Faktoriel kompleksitet er repræsenteret ved symbolet O(n!). Denne funktion vokser også meget hurtigt og er derfor ikke skalerbar.
Konklusion
Denne artikel dækkede Big O-analyse og hvordan man beregner det. Vi diskuterede også de forskellige kompleksiteter og diskuterede deres skalerbarhed.
Dernæst vil du måske øve Big O-analyse på Python-sorteringsalgoritmen.