AlegsaOnline.com

Big O-notation: definition, komplexitet och algoritmanalys

Big O-notation: definition, komplexitet och algoritmanalys — förstå tids- och minneskomplexitet för att optimera algoritmer och skriva effektiv kod.

Författare: Leandro Alegsa

26-01-2026

Inom matematik och datavetenskap är Big O-notationen ett standardverktyg för att beskriva och jämföra tillväxttakten hos olika funktioner. I praktiken används den framför allt för att jämföra effektiviteten hos olika algoritmer genom att ange hur mycket minne som krävs och hur lång tid (antal grundläggande operationer) som behövs för att slutföra beräkningen när indata växer.

Big O-notationen hjälper också till att klassificera problem efter svårighetsgrad, det vill säga i vilken komplexitetsklass ett problem ligger. Historiskt användes liknande notation redan av Paul Bachmann (1837–1920) i den andra upplagan av "Analytische Zahlentheorie" (1896), och Edmund Landau (1877–1938) gjorde notationerna välkända — därför kallas de ofta för Landau-symboler.

Namnet "Big O" kommer från engelska uttrycket "order of the function" och avser funktioners tillväxt i förhållande till varandra. I praktisk algoritmanalys används Big O för att ange en övre gräns på tillväxttakten — alltså ett säkert mått på hur mycket tid eller resurser en algoritm kan kräva i ett värsta fall. På så sätt kan algoritmer grupperas efter hur dåligt de kan prestera i största skala: en algoritm med O ( 1 ) {\displaystyle O(1)} $O(1)$ växer mycket långsammare än en med O ( n ! ) {\displaystyle O(n!)} $O(n!)$ , vilket gör att firstnämnda i praktiken nästan alltid kommer vara snabbare för stora n oavsett hårdvara.

Mer formellt, givet två positiva funktioner f ( x ) {\displaystyle f(x)} f(x) och g ( x ) {\displaystyle g(x)} $g(x)$ , säger vi att f {\displaystyle f} är i det stora O av g {\displaystyle g} (skrivet f ∈ O ( g ) {\displaystyle f\in O(g)} $f\in O(g)$ ) om det finns positiva konstanter k och x0 sådana att för alla x ≥ x0 gäller f ( x ) ≤ k ⋅ $f(x)\leq k\cdot g(x)$ för en viss konstant k {\displaystyle k}. I enklare ord: f växer inte snabbare än en konstant gånger g för alla tillräckligt stora argument.

Vanliga komplexitetsklasser (tidskomplexitet)

O(1) — konstant tid: ex. åtkomst till ett element i en array med index. Den exekveringstid som krävs ändras inte med n.
O(log n) — logaritmisk tid: ex. binärsökning i en sorterad lista.
O(n) — linjär tid: ex. enkel linjär sökning, eller en enkel loop som går igenom alla element.
O(n log n) — typiskt för effektiva sorteringsalgoritmer som mergesort och heapsort.
O(n^2) — kvadratisk tid: ex. två nästlade loopar över samma data (enkla sorteringsalgoritmer som bubble sort i sämsta fall).
O(n^k) — polynomisk tid (k>1): dyrare nästlade loopar eller polynomiella beräkningar.
O(2^n) — exponentiell tid: många bruteforce-recursive lösningar, t.ex. generering av alla delmängder.
O(n!) — faktoriell tid: t.ex. analys av alla permutationen av n element (exempelvis vissa varianter av lösningar till Travelling Salesman i brute-force).

Tids- vs. minneskomplexitet

Tidskomplexitet (time complexity) beskriver hur antalet operationer växer med indata (n). Minneskomplexitet (space complexity) beskriver hur mycket extra minne som behövs utöver indata. En algoritm kan vara snabb men kräva mycket minne eller använda lite minne men vara långsam — Big O kan användas för båda typerna.

Bästa, genomsnittliga och sämsta fall

Big O anger vanligtvis en övre gräns (sämsta fall). Det finns också beteckningar för andra fall:

Ω (Omega) beskriver en nedre gräns (bästa fall).
Θ (Theta) används när en funktion har både samma övre och nedre gräns asymptotiskt (precis tillväxtklass).
Genomsnittlig (average-case) komplexitet försöker beskriva förväntad kostnad under en given sannolikhetsfördelning av indata.

Regler för förenkling

Konstanter kan ignoreras: O(2n) = O(n).
Endast dominerande termer räknas: O(n + n^2) = O(n^2).
Ofta multipliceras komplexiteter vid nästlade strukturer: en loop inom en loop ger O(n)·O(n) = O(n^2).
Sammanfogning (addition) används för sekventiella steg och tar den större termen: O(f) + O(g) = O(max(f,g)).

Hur man analyserar en algoritm — enkla steg

Identifiera den grundläggande operationen som påverkar prestanda mest (t.ex. jämförelser eller byten).
Räkna hur många gånger den operationen utförs som funktion av indatastorleken n.
Förenkla uttrycket genom att ta bort konstanta faktorer och lägre ordningens termer.
Ange den resulterande klassen med Big O.

Exempel: En enkel for-loop som körs n gånger gör en konstant mängd arbete per iteration → O(n). Två nästlade for-loopar, var och en över n, ger O(n^2).

Praktiska aspekter och råd

Big O ger asymptotisk information — för små n kan en "sämre" Big O ändå vara snabbare på grund av lägre konstantfaktorer eller bättre cacheanpassning.
Amortiserad komplexitet: vissa operationer kan vara O(1) i genomsnitt över många operationer även om enstaka operationer är dyrare (t.ex. dynamiska arrayer som expanderar).
Välj algoritm efter problemstorlek och tillgängliga resurser. För mycket stora n är skillnaden mellan O(n log n) och O(n^2) ofta avgörande.
Kom ihåg att Big O inte tar hänsyn till konstantkostnader, parallellism eller praktiska implementationseffekter — det är ett teoretiskt verktyg som kompletterar mätningar och profilering.

Sammanfattning

Big O-notationen är ett kraftfullt sätt att beskriva hur algoritmers tid- och minnesbehov växer med indata. Genom att förstå vanliga komplexitetsklasser, förenklingsregler och hur man analyserar kod kan man bättre jämföra och välja algoritmer för verkliga problem. Använd Big O tillsammans med mätningar och hänsyn till praktiska faktorer för att få en komplett bild av en algoritms prestanda.

Exempel

I följande exempel används kod som är skriven i Python. Observera att detta inte är en fullständig lista över Big O-typer.

Konstant

O ( 1 ) {\displaystyle O(1)} $O(1)$ tar alltid lika lång tid oavsett vad som används. Ta till exempel en funktion som tar emot ett heltal (kallat x) och returnerar dubbelt så mycket som dess värde:

def double(x): return x * 2 #Returnerar värdet av x gånger 2

Efter att ha tagit emot inmatningen tar denna funktion alltid ett steg för att returnera ett utdata. Det är konstant eftersom det alltid tar lika lång tid, så det är O ( 1 ) {\displaystyle O(1)} $O(1)$ .

Linjär

O ( n ) {\displaystyle O(n)} $O(n)$ ökar med storleken på inmatningen, som representeras av n {\displaystyle n} . Till exempel för följande funktion som accepterar n och returnerar alla tal från 1 till n:

def count(n): i = 1 #Skapa en räknare kallad "i" med värdet 1 while i <= n: # Medan i är mindre än eller lika med n print(i) #Skriv ut värdet av i i i = i + 1 #Redefiniera i som "värdet av i + 1"

Om vi skulle ange värdet 5 skulle detta ge ut $1,2,3,4,5$ Det krävs 5 slingor för att slutföra. På samma sätt, om vi anger 100, skulle det ge ut $1,2,3...98,99,100$ , vilket kräver 100 slingor för att slutföra. Om inmatningen är n {\displaystyle n} är algoritmens körtid exakt n {\displaystyle n} slingor varje gång, och därför är den O ( n ) {\displaystyle O(n)} $O(n)$ .

Factorial

O ( n ! ) {\displaystyle O(n!)} $O(n!)$ ökar i faktoriella mängder, vilket innebär att den tid som krävs ökar kraftigt med mängden indata. Säg till exempel att vi vill besöka fem städer runt om i världen och vill se alla möjliga ordningar (permutationer). En algoritm som vi skulle kunna skriva med hjälp av Pythons itertools-bibliotek är följande:

import itertools #Import itertools-biblioteket cities = ['London', 'Paris', 'Berlin', 'Amsterdam', 'Rom'] #En array med våra valda städer def permutations(cities): #Vi tar en matris av städer som indata: for i in itertools.permutations(cities): #För varje permutation av våra objekt (tilldelas variabeln "i") print(i) #Output i

Algoritmen beräknar varje unik permutation av våra städer och ger sedan ut den. Exempel på utdata är följande:

("London", "Paris", "Berlin", "Amsterdam", "Rom") ("London", "Paris", "Berlin", "Rom", "Amsterdam") ("London", "Paris", "Amsterdam", "Berlin", "Rom") ... ("Rom", "Amsterdam", "Paris", "Berlin", "London") ("Rom", "Amsterdam", "Berlin", "London", "Paris") ("Rom", "Amsterdam", "Berlin", "London", "Paris") ("Rom", "Amsterdam", "Berlin", "Paris", "London")

Här är vår ingångslista 5 objekt, och för varje val minskar de återstående alternativen med 1. Med andra ord väljer våra 5 ingångar $5\times 4\times 3\times 2\times 1$ objekt (eller 5 ! {\displaystyle 5!} $5!$ ). Om vår indata är n {\displaystyle n} städer lång, är antalet utdata n ! {\displaystyle n!} $n!$ ; i allmänhet, om vi antar att vi går igenom varje permutation, krävs det O ( n ! ) {\displaystyle O(n!)} $O(n!)$ slingor för att slutföra den.

Little-o notation

Ett begrepp som är besläktat med Big-O-notation är Little-O-notation. Big-O används för att säga att en funktion inte växer snabbare än en annan funktion, medan little-o används för att säga att en funktion växer långsammare än en annan funktion. Om två funktioner växer i samma takt kan big-O användas, men inte little-o. Skillnaden mellan big-O och little-o liknar skillnaden mellan ≤ {\displaystyle \leq } $\leq$ och < {\displaystyle <} $<$ .

Om f ( x ) {\displaystyle f(x)} växer långsammare än g ( x ) {\displaystyle g(x)} $g(x)$ , så är $f(x)\in O(g(x))$ och $f(x)\in o(g(x))$ .
Om f ( x ) {\displaystyle f(x)} växer i samma takt som g ( x ) {\displaystyle g(x)} $g(x)$ , så är $f(x)\in O(g(x))$ men f ( x ) ∉ $f(x)\not \in o(g(x))$ .
Om f ( x ) {\displaystyle f(x)} växer snabbare än g ( x ) {\displaystyle g(x)} $g(x)$ , då f ( x ) ∉ $f(x)\not \in O(g(x))$ och f ( x ) ∉ $f(x)\not \in o(g(x))$ .

Frågor och svar

F: Vad är Big O-notation?

S: Big O-notation är ett sätt att jämföra tillväxttakten för olika funktioner, som ofta används för att jämföra effektiviteten hos olika algoritmer genom att beräkna hur mycket minne och tid det tar att genomföra. Det kan också användas för att identifiera hur komplext ett problem är.

F: Vem var den första som använde denna notation?

S: Matematikern Paul Bachmann (1837-1920) var den första som använde denna notation i sin bok "Analytische Zahlentheorie" 1896.

F: Vad står Big O för?

S: Big O står för "funktionens ordning", vilket avser funktionernas tillväxttakt.

F: Hur används Big O?

S: Big O-notationen används för att hitta en övre gräns (högsta möjliga belopp) för funktionens tillväxthastighet, vilket innebär att man räknar ut den längsta tid det tar att omvandla en inmatning till en utmatning. Detta innebär att algoritmer kan grupperas efter hur lång tid de tar i värsta fall, där den längsta vägen tas varje gång.

F: Vad är Landau-symboler?

S: Landau-symbolerna hänvisar till Big O-notationen, uppkallad efter Edmund Landau (1877-1938) som gjorde denna notation populär.

F: Varför är Big O användbart?

S: Big O gör det möjligt att mäta hastigheten utan att behöva köra program på datorer, eftersom den alltid utgår från värsta tänkbara scenarier, vilket gör den konsekvent oavsett skillnader i hårdvara mellan datorer. Det visar också hur effektiv en algoritm är utan att man behöver köra den på en dator.