Big O-notation

Snabböversikt

Big O beskriver en asymptotisk övre gräns för hur arbetet eller minnesåtgången kan växa när indata blir större. Det är inte en klocka som mäter exakt körningstid.

Jämför tillväxtkurvor

INTERACTIVE / LIVE

Big O-graf

Ändra antalet element och välj vilka kurvor som ska visas.

Live demo

Visuell referens

Översikt över hur Big O-komplexiteter växer (illustration, inte uppmätt tid)

Bilden illustrerar koncepten, inte uppmätta körtider. Använd visualiseraren ovan för att ändra indatastorlek och jämföra kurvor.

Vanliga komplexitetsklasser

Klass	Namn	Exempel
`O(1)`	Konstant	Åtkomst till arrayindex
`O(log n)`	Logaritmisk	Binärsökning
`O(√n)`	Kvadratrot	Enkel provdivision upp till √n
`O(n)`	Linjär	Gå igenom en lista
`O(n log n)`	Linjärlogaritmisk	Mergesortering
`O(n³)`	Kubisk	Tre nästlade loopar
`O(n²)`	Kvadratisk	Två nästlade loopar
`O(2ⁿ)`	Exponentiell	Naiv genomgång av alla delmängder
`O(n!)`	Fakultet	Generera permutationer

Se även komplexitetskartan med separata lektionssidor för alla nio klasser.

Så analyserar du ett uttryck

Om antalet operationer kan skrivas som 4n² + 7n + 3 dominerar termen n² när n blir stort. Därför kan vi skriva O(n²). O(n³) vore också en övre gräns, men är mindre informativ.

Exempel: linjär sökning

static int FindIndex(int[] values, int target)
{
    for (int i = 0; i < values.Length; i++)
        if (values[i] == target) return i;
    return -1;
}

#include <vector>
int findIndex(const std::vector<int>& values, int target) {
    for (std::size_t i = 0; i < values.size(); ++i) {
        if (values[i] == target) return static_cast<int>(i);
    }
    return -1;
}

I sämsta fall jämför vi med alla n värden. Tidskomplexiteten blir O(n) och det extra minnet är O(1).

Missförstånd att undvika

Big O anger inte antal millisekunder.
En kvadratisk algoritm kan vara snabbare för en mycket liten lista.
O(1) innebär en kostnad som inte växer med indatastorleken, inte att inget arbete utförs.
Det är skillnad på förväntad kostnad och sämsta fall.

Flera oberoende indatastorlekar

Om programmet jämför varje användare med varje behörighet kan arbetet vara O(u × p) snarare än O(n²). Antalet användare och behörigheter växer inte alltid tillsammans. Skriv därför vad variablerna betyder.

Övre gräns och tät gräns

Big O beskriver en asymptotisk övre gräns, Θ (Theta) en tät gräns och Ω (Omega) en undre gräns. I vardagligt tal används ofta Big O när man menar den exakta tillväxtklassen, men i en noggrann analys bör skillnaden framgå. En linjär funktion är till exempel O(n²), men Θ(n) berättar mer.

Före optimering

Ta reda på om kostnaden faktiskt kommer från beräkningar, minnesallokering, disk eller nätverk. Komplexitetsanalys visar möjliga skalningsproblem, medan profilering visar var den riktiga tiden går. Mät med representativa indata.

Läs vidare

Extern referensGeeksforGeeks: Big O AnalysisLäs om hur arbetsmängden växer med indatans storlek.Relaterad lektionTidskomplexitetLär dig analysera hur många steg algoritmen behöver.Relaterad lektionMinneskomplexitetUndersök hur minnesbehovet växer.

Kontrollfråga

TESTA KUNSKAPEN

Vad händer med antalet operationer i en O(n²)-algoritm om indata fördubblas?

Visa förklaring

För större n dominerar n². (2n)² = 4n². Konstanter och mindre termer kan påverka små indata.