Kvadratisk (O(n²))

Kort sammanfattning: Arbete eller antalet lagrade celler växer proportionellt mot kvadraten på indatastorleken.

Gå direkt till: Tidskomplexitet · Minneskomplexitet · Övning

Förstå tillväxten

Att kontrollera varje ordnat par bland n objekt kräver n × n jämförelser om varje par kostar lika mycket. Ett rutnät med n rader och n kolumner har lika många celler.

En fördubbling från n till 2n fyrdubblar antalet ordnade par: (2n)² = 4n². Om bara oordnade distinkta par testas blir antalet n(n-1)/2, vilket fortfarande är Θ(n²) eftersom den ledande termen är kvadratisk.

Att undersöka alla par ger en kvadrat

Om varje element jämförs med alla n elementen blir antalet jämförelser n × n = n². Det omfattar även att ett element paras med sig självt och att (a,b) skiljs från (b,a). Om du bara undersöker olika oordnade par blir antalet n(n-1)/2, fortfarande Θ(n²).

Kvadratisk tid finns också i exempelvis insertion sort i värsta fall. När element i ska placeras kan upp till i tidigare element behöva flyttas. Summan 1 + 2 + ... + (n-1) växer kvadratiskt. På redan sorterade data kan samma algoritm däremot arbeta linjärt.

Två nästlade loopar är ingen automatisk garanti för O(n²). Om den inre loopen fortsätter från sin förra position kan det totala antalet iterationer vara linjärt. Räkna de faktiska gränserna.

Ett genomräknat exempel

För 10 element finns 100 ordnade par, för 20 finns 400 och för 100 finns 10 000. Därför kan en kvadratisk algoritm fungera bra på små exempel men snabbt bli dyr på stora mängder data.

Ordnade och oordnade par

Med fyra personer finns 16 ordnade par inklusive självpar. Om uppgiften är att undersöka om varje par olika personer känner varandra räcker det med 4 × 3 / 2 = 6 kontroller. Vid 100 personer blir motsvarande antal 10 000 och 4 950.

När antalet personer fördubblas från 100 till 200 ökar antalet ordnade par från 10 000 till 40 000. De oordnade paren ökar från 4 950 till 19 900. Exakta antal skiljer sig, men båda är kvadratiska.

Tidskomplexitet

Exempel för tidsanalys: Alla par av element.

Två fullständiga nästlade loopar gör n iterationer var och därför n² anrop till den innersta operationen. Det förutsätter att själva operationen kostar O(1). Jämförelse av långa strängar kan vara dyrare. Om den inre loopen avslutas tidigt eller har en gräns som beror på i måste antalet summeras, inte bara multipliceras.

Härled antalet iterationer

Om två loopar vardera går n varv utförs innersta operationen Θ(n²) gånger. Om den inre börjar på j = i + 1 blir antalet (n-1) + (n-2) + ... + 0 = n(n-1)/2, vilket fortfarande är Θ(n²).

Om den innersta operationen dessutom gör en linjär sökning kan totalen bli Θ(n³). För insertion sort spelar också ordningen på indata roll: redan sorterade data ger ofta Θ(n) tid, medan omvänd ordning ger Θ(n²) förflyttningar. Ange vilket fall analysen gäller.

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]);

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]);

Analys: Två fullständiga nästlade loopar ger O(n²) anrop om den inre operationen har konstant kostnad.

C++-exemplet visar samma grundidé, men kompilator, container och anropade funktioner måste ingå i en fullständig komplexitetsanalys.

Minneskomplexitet

Exempel för minnesanalys: En grannmatris.

En boolesk matris med n × n positioner innehåller n² celler och använder O(n²) minne. En grannmatris för en graf är ett praktiskt exempel, men om matrisen räknas som extra minne eller själva indata beror på systemets gränser. Två nästlade loopar behöver vanligtvis bara två räknare och alltså O(1) extra minne.

En par-loop behöver ingen matris

En loop som jämför alla par kan nöja sig med två index och ett tillfälligt resultat: Θ(1) extra minne. En n × n-matris lagrar däremot Θ(n²) celler på samma gång. För en graf kan en sådan grannmatris ge direkt O(1)-åtkomst till frågan om en kant finns mellan två hörn.

Om grafen är gles kan en grannlista med Θ(n + e) lagringsbehov vara lämpligare, där e är antalet kanter. Matriser kan vara bekväma för täta grafer men dyra om bara några få par har relationer. Minnesbehovet beror på vad som sparas, inte hur många nästlade loopar koden har.

C#

C# | Quadratic.cs

bool[,] seen = new bool[n, n];

C++

C++ | quadratic.cpp

#include <vector>

std::vector<std::vector<bool>> seen(n, std::vector<bool>(n));

Analys: En n × n-matris tar O(n²) extra minne; looparna i sig kräver inte O(n²) minne.

Minnesgränsen avser allokerade element och aktiva anropsramar; faktisk overhead beror på runtime, allocator och elementtyp.

När duger kvadratiska algoritmer?

För små indata, enkla implementationer eller problem där alla par faktiskt måste rapporteras kan Θ(n²) vara rimligt. Om utdata innehåller varje par kräver själva utskriften redan Ω(n²) tid. Vid dubblettsökning kan däremot sortering eller hashning minska antalet direkta parjämförelser.

En enkel insertion sort kan vara effektiv på små eller nästan sorterade arrayer trots sitt kvadratiska värsta fall, medan merge sort har Θ(n log n) även när indata är besvärlig. Asymptotisk tillväxt är bara en del av valet.

Praktiskt exempel: kontrollera enheter parvis

Ett enkelt spelsystem kan jämföra varje enhet med varje annan enhet för att upptäcka närhet. Med n enheter blir det Θ(n²) jämförelser, även om de flesta enheterna står långt ifrån varandra. Om relationen är symmetrisk kan i < j undvika dubbelkontroller och ungefär halvera arbetet, men inte ändra komplexitetsklassen.

En spatial grid, quadtree eller annan bredfasstruktur kan minska antalet tänkbara par i många scener, men den faktiska garantin beror på fördelning och implementation. Själva parloopen kan använda konstant extra minne, medan en matris över alla relationer kräver Θ(n²) celler.

Vanligt misstag

Se upp: Nästlade loopar innebär inte alltid O(n²). Om den inre loopens index fortsätter där det slutade kan det sammanlagda antalet iterationer vara linjärt. Analysera gränserna först.

Testa kunskaperna

Räkna både ordnade och oordnade par för n = 5 och beräkna sedan antalet bytes i en n × n byte-matris.

1. Definiera exakt vad n betyder i exemplet.
2. Räkna huvudoperationen i bästa och värsta fall där det är relevant.
3. Räkna största samtidiga minnesmängd.
4. Kontrollera resultatet i Big O-visualiseraren.

Fortsätt läsa

Big O-översikt · Tidskomplexitet · Minneskomplexitet · Jämför klasser