Big O Analysis är en teknik för att analysera och rangordna effektiviteten hos algoritmer.
Detta gör att du kan välja de mest effektiva och skalbara algoritmerna. Den här artikeln är ett Big O Cheat Sheet som förklarar allt du behöver veta om Big O Notation.
Innehållsförteckning
Vad är Big O Analysis?
Big O Analysis är en teknik för att analysera hur väl algoritmer skalas. Specifikt frågar vi hur effektiv en algoritm är när indatastorleken ökar.
Effektivitet är hur väl systemresurserna används när man producerar en utdata. De resurser vi i första hand sysslar med är tid och minne.
Därför, när vi utför Big O Analysis, är frågorna vi ställer:
Svaret på den första frågan är algoritmens rymdkomplexitet, medan svaret på den andra är dess tidskomplexitet. Vi använder en speciell notation som kallas Big O Notation för att uttrycka svar på båda frågorna. Detta kommer att behandlas härnäst i Big O Cheat Sheet.
Förutsättningar
Innan jag går vidare måste jag säga att för att få ut det mesta av detta Big O Cheat Sheet måste du förstå lite algebra. Dessutom, eftersom jag kommer att ge Python-exempel, är det också användbart att förstå lite Python. En djupgående förståelse är onödig eftersom du inte kommer att skriva någon kod.
Hur man utför Big O-analys
I det här avsnittet kommer vi att täcka hur man utför Big O Analysis.
När du utför Big O Complexity Analysis är det viktigt att komma ihåg att algoritmens prestanda beror på hur indata är strukturerad.
Till exempel går sorteringsalgoritmer snabbast när data i listan redan är sorterade i rätt ordning. Det är det bästa scenariot för algoritmens prestanda. Å andra sidan är samma sorteringsalgoritmer långsammast när data struktureras i omvänd ordning. Det är det värsta scenariot.
När vi utför Big O Analysis tar vi bara hänsyn till det värsta scenariot.
Rymdkomplexitetsanalys
Låt oss börja detta Big O Cheat Sheet med att täcka hur man utför rymdkomplexitetsanalys. Vi vill överväga hur det extra minnet som en algoritm använder skalar när ingången blir större och större.
Till exempel använder funktionen nedan rekursion för att loopa från n till noll. Den har en rymdkomplexitet som är direkt proportionell mot n. Detta beror på att när n växer så ökar antalet funktionsanrop på anropsstacken. Så den har en rymdkomplexitet av O(n).
def loop_recursively(n):
if n == -1:
return
else:
print(n)
loop_recursively(n - 1)
En bättre implementering skulle dock se ut så här:
def loop_normally(n):
count = n
while count >= 0:
print(count)
count =- 1
I algoritmen ovan skapar vi bara en extra variabel och använder den för att loopa. Om n blev större och större skulle vi ändå bara använda en extra variabel. Därför har algoritmen konstant rymdkomplexitet, betecknad med ”O(1)”-symbolen.
Genom att jämföra rymdkomplexiteten för de två algoritmerna ovan drog vi slutsatsen att while-loopen var effektivare än rekursion. Det är huvudsyftet med Big O Analysis: att analysera hur algoritmer förändras när vi kör dem med större indata.
Tidskomplexitetsanalys
När vi utför tidskomplexitetsanalyser är vi obekymrade över tillväxten i den totala tiden som algoritmen tar. Snarare är vi oroade över ökningen av beräkningssteg som tagits. Detta beror på att den faktiska tiden beror på många systemiska och slumpmässiga faktorer som är svåra att ta hänsyn till. Så vi spårar bara tillväxten av beräkningssteg och antar att varje steg är lika.
För att demonstrera tidskomplexitetsanalys, överväg följande exempel:
Anta att vi har en lista över användare där varje användare har ett ID och ett namn. Vår uppgift är att implementera en funktion som returnerar användarens namn när det ges ett ID. Så här kan vi göra 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 lista över användare går vår algoritm igenom hela användarens array för att hitta användaren med rätt ID. När vi har 3 användare utför algoritmen 3 iterationer. När vi har 10 ger den 10.
Därför är antalet steg linjärt och direkt proportionellt mot antalet användare. Så vår algoritm har linjär tidskomplexitet. Men vi kan förbättra vår algoritm.
Anta att vi istället för att lagra användare i en lista, lagrade dem i en ordbok. Då skulle vår algoritm för att leta upp en användare se ut så här:
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)
Med den här nya algoritmen, anta att vi hade 3 användare i vår ordbok; vi skulle utföra flera steg för att få användarnamnet. Och anta att vi hade fler användare, säg tio. Vi skulle utföra samma antal steg som tidigare för att få användaren. När antalet användare växer förblir antalet steg för att få ett användarnamn konstant.
Därför har denna nya algoritm konstant komplexitet. Det spelar ingen roll hur många användare vi har; antalet beräkningssteg som tas är detsamma.
Vad är Big O Notation?
I föregående avsnitt diskuterade vi hur man beräknar Big O-utrymmet och tidskomplexiteten för olika algoritmer. Vi använde ord som linjär och konstant för att beskriva komplexitet. Ett annat sätt att beskriva komplexitet är att använda Big O Notation.
Big O Notation är ett sätt att representera en algoritms rymd- eller tidskomplexitet. Notationen är relativt enkel; det är ett O följt av parenteser. Inom parentesen skriver vi en funktion av n för att representera den speciella komplexiteten.
Linjär komplexitet representeras av n, så vi skulle skriva det som O(n) (läs som ”O av n”). Konstant komplexitet representeras av 1, så vi skulle skriva det som O(1).
Det finns fler komplexiteter, som vi kommer att diskutera i nästa avsnitt. Men i allmänhet, för att skriva en algoritms komplexitet, följ följande steg:
Resultatet av det blir termen vi använder inom våra parenteser.
Exempel:
Tänk på följande 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 kommer vi att beräkna algoritmens Big O Time-komplexitet.
Vi skriver först en matematisk funktion av nf(n) för att representera antalet beräkningssteg algoritmen tar. Kom ihåg att n representerar indatastorleken.
Från vår kod utför funktionen två steg: ett för att beräkna antalet användare och det andra för att skriva ut antalet användare. Sedan, för varje användare, utför den två steg: ett för att skriva ut indexet och ett för att skriva ut användaren.
Därför kan den funktion som bäst representerar antalet beräkningssteg som tagits skrivas som f(n) = 2 + 2n. Där n är antalet användare.
När vi går vidare till steg två väljer vi den mest dominerande termen. 2n är en linjär term och 2 är en konstant term. Linjär är mer dominant än konstant, så vi väljer 2n, den linjära termen.
Så vår funktion är nu f(n) = 2n.
Det sista steget är att eliminera koefficienter. I vår funktion har vi 2 som koefficient. Så vi tar bort det. Och funktionen blir f(n) = n. Det är termen vi använder mellan våra parenteser.
Därför är tidskomplexiteten för vår algoritm O(n) eller linjär komplexitet.
Olika Big O-komplexiteter
Det sista avsnittet i vårt Big O Cheat Sheet kommer att visa dig olika komplexiteter och tillhörande grafer.
#1. Konstant
Konstant komplexitet innebär att algoritmen använder en konstant mängd utrymme (när man utför rymdkomplexitetsanalys) eller ett konstant antal steg (när man utför tidskomplexitetsanalys). Detta är den mest optimala komplexiteten eftersom algoritmen inte behöver ytterligare utrymme eller tid när indata växer. Den är därför väldigt skalbar.
Konstant komplexitet representeras som O(1). Det är dock inte alltid möjligt att skriva algoritmer som körs i konstant komplexitet.
#2. Logaritmisk
Logaritmisk komplexitet representeras av termen O(log n). Det är viktigt att notera att om logaritmbasen inte är specificerad i datavetenskap, antar vi att den är 2.
Därför är log n log2n. Logaritmiska funktioner är kända för att växa snabbt till en början och sedan sakta ner. Detta innebär att de skalar och arbetar effektivt med ett allt större antal n.
#3. Linjär
För linjära funktioner, om den oberoende variabeln skalas med en faktor p. Den beroende variabeln skalar med samma faktor p.
Därför växer en funktion med linjär komplexitet med samma faktor som indatastorleken. Om indatastorleken fördubblas kommer antalet beräkningssteg eller minnesanvändning också att göra det. Linjär komplexitet representeras av symbolen O(n).
#4. Linjärtmisk
O (n * log n) representerar linjärtmiska funktioner. Linjärtmiska funktioner är en linjär funktion multiplicerad med logaritmfunktionen. Därför ger en linjärtmisk funktion resultat som är något större än linjära funktioner när log n är större än 1. Detta beror på att n ökar när det multipliceras med ett tal större än 1.
Log n är större än 1 för alla värden på n större än 2 (kom ihåg att log n är log2n). Därför, för alla värden på n större än 2, är linjära funktioner mindre skalbara än linjära funktioner. Varav n är större än 2 i de flesta fall. Så linaritmiska funktioner är i allmänhet mindre skalbara än logaritmiska funktioner.
#5. Kvadratisk
Kvadratisk komplexitet representeras av O(n2). Detta innebär att om din inmatningsstorlek ökar med 10 gånger, ökar antalet steg som tas eller utrymme som används med 102 gånger eller 100! Detta är inte särskilt skalbart, och som du kan se från grafen, blåser komplexiteten upp väldigt snabbt.
Kvadratisk komplexitet uppstår i algoritmer där man loopar n gånger, och för varje iteration loopar man n gånger igen, till exempel i Bubble Sort. Även om det i allmänhet inte är idealiskt, har du ibland inget annat val än att implementera algoritmer med kvadratisk komplexitet.
#6. Polynom
En algoritm med polynomkomplexitet representeras av O(np), där p är ett konstant heltal. P representerar den ordning i vilken n höjs.
Denna komplexitet uppstår när du har ett antal kapslade loopar. Skillnaden mellan polynomkomplexitet och kvadratisk komplexitet är kvadratisk i storleksordningen 2, medan polynom har valfritt tal större än 2.
#7. Exponentiell
Exponentiell komplexitet växer till och med snabbare än polynomkomplexitet. I Math är standardvärdet för exponentialfunktionen konstanten e (Eulers tal). Inom datavetenskap är dock standardvärdet för exponentialfunktionen 2.
Exponentiell komplexitet representeras av symbolen O(2n). När n är 0, är 2n 1. Men när n ökas till 5, blåser 2n upp till 32. En ökning av n med ett fördubblar det föregående talet. Därför är exponentialfunktioner inte särskilt skalbara.
#8. Faktoriell
Faktoriell komplexitet representeras av symbolen O(n!). Denna funktion växer också mycket snabbt och är därför inte skalbar.
Slutsats
Den här artikeln täckte Big O Analysis och hur man beräknar den. Vi diskuterade också de olika komplexiteten och diskuterade deras skalbarhet.
Därefter kanske du vill öva Big O-analys på Python-sorteringsalgoritmen.