Tidskomplexitet

Grunder

Snabböversikt

Tidskomplexitet beskriver hur mängden arbete förändras när indata blir större. Den anger inte exakt tid i sekunder. Om dubbelt så mycket indata ungefär fördubblar antalet iterationer använder vi ofta en linjär modell som O(n).

Vad räknas som en operation?

Välj en operation som representerar arbetet, till exempel en jämförelse eller en läsning från en array. I modellen antas en enkel operation ha ungefär konstant kostnad. Hårdvara, cacheminne och språkets implementation kan ändå påverka verklig tid.

Ange alltid förutsättningarna

Bästa, genomsnittliga och sämsta fall kan skilja sig åt. Skriv vilket fall du analyserar och om indata exempelvis måste vara sorterad.

Tre exempel

Konstant

C#

C# | Constant.cs

int first = values[0]; // O(1) om arrayen inte är tom

C++

C++ | Constant.cpp

int first = values.at(0); // O(1), throws if empty

En läsning görs oavsett hur stor arrayen är.

Linjär

C#

C# | Linear.cs

foreach (int value in values)
    Console.WriteLine(value); // O(n) totalt

C++

C++ | Linear.cpp

for (int value : values)
    std::cout << value << '\n'; // O(n) total

Alla n värden besöks en gång.

Kvadratisk

C#

C# | Quadratic.cs

for (int i = 0; i < values.Length; i++)
    for (int j = 0; j < values.Length; j++)
        Compare(values[i], values[j]); // O(n²) totalt

C++

C++ | Quadratic.cpp

for (std::size_t i = 0; i < values.size(); ++i)
    for (std::size_t j = 0; j < values.size(); ++j)
        compare(values[i], values[j]); // O(n^2)

De nästlade looparna gör n × n jämförelser.

Analysera kod steg för steg

1. Bestäm vad n betyder. Är det antalet objekt, tecken eller något annat?
2. Välj en relevant operation. Räkna till exempel jämförelser i stället för källkodsrader.
3. Räkna upprepningar. En loop över hela indata ger ofta O(n). Halveras sökområdet blir det ofta O(log n).
4. Kombinera delarna. Efterföljande delar adderas, medan nästlade loopar ofta multipliceras.
5. Behåll den dominerande termen. 3n² + 2n + 8 kan beskrivas som O(n²).

Bästa, genomsnittliga och sämsta fall

Linjär sökning hittar målet direkt om det ligger först. I sämsta fall granskar den hela listan. Om alla positioner är lika sannolika blir det genomsnittliga antalet jämförelser proportionellt mot n när målet finns.

Vad teorin inte säger

O(n log n) är inte automatiskt snabbare än O(n²) för varje liten lista. Minnesallokeringar, cachebeteende och konstanter spelar roll. Använd komplexitet för att förstå skalning och mätning för att jämföra verkliga implementationer.

Två loopar betyder inte alltid kvadratisk tid

Två efterföljande loopar över n objekt ger n + n iterationer och är fortfarande linjära. Nästlade loopar är ofta kvadratiska, men bara när båda gör ungefär n iterationer. En triangulär nästlad loop gör cirka n(n-1)/2 iterationer och har fortfarande tillväxten Θ(n²).

Dold kostnad i hjälpfunktioner

En ensam rad som collection.Contains(value) är inte automatiskt konstant. Det beror på samlingens typ. En lista kan behöva söka linjärt, medan en hashtabell normalt har annan förväntad kostnad. Studera metoden som anropas, inte bara looparna runt den.

Mäta på ett bra sätt

Testa flera indatastorlekar i en konsekvent miljö. Anteckna om data är slumpad, sorterad eller utformad för att ge dåliga fall. Ett snabbt test med få värden säger sällan mycket om långsiktig skalning.

Läs vidare

↗Extern referensGeeksforGeeks: tidskomplexitetLär dig analysera hur många steg algoritmen behöver.↗Relaterad lektionBig O-notationLäs om hur arbetsmängden växer med indatans storlek.↗Relaterad lektionMinneskomplexitetUndersök hur minnesbehovet växer.