Kubisk (O(n³))

Kort sammanfattning: Antalet operationer eller minnesceller växer med kuben på indatastorleken.

Gå direkt till: Tidskomplexitet · Minneskomplexitet · Övning

Förstå tillväxten

När en process undersöker varje ordnad trippel väljer den ett index för första, andra och tredje objektet. Varje val har n alternativ och antalet kombinationer blir n × n × n.

Om n fördubblas blir en kubisk mängd åtta gånger större: (2n)³ = 8n³. Om n halveras blir den åtta gånger mindre. Kubisk tillväxt är asymptotiskt långsammare än exponentiell tillväxt, men kan ändå bli dyr vid måttliga indatastorlekar.

Tre oberoende dimensioner

Om indexen i, j och k vardera kan anta n värden finns n³ ordnade tripplar. Det tredje indexet multiplicerar varje par (i,j) med ytterligare n alternativ. När n fördubblas blir antalet kombinationer åtta gånger större.

Kubisk tid uppstår också i vissa dynamiska program med tre dimensioner. Exempelvis använder Floyd-Warshall för kortaste vägar en trippelloop över grafens hörn och utför Θ(v³) uppdateringar, där v är antalet hörn.

Titta ändå på looparnas verkliga gränser. Om en loop alltid körs tre gånger är den dimensionen en konstant och ger inte ytterligare en faktor n. Om den innersta operationen i sin tur tar linjär tid kan hela algoritmen bli dyrare än kubisk.

Ett genomräknat exempel

För n = 10 finns 1 000 tripplar, för n = 20 finns 8 000 och för n = 100 en miljon. En byte-kub med n = 1 000 kräver redan ungefär en miljard bytes före overhead.

Räkna tripplar

Fem möjliga indexvärden ger 5 × 5 × 5 = 125 ordnade tripplar. Tio ger 1 000 och tjugo ger 8 000. Om varje kombination kunde behandlas på exakt en mikrosekund skulle 20 värden ge cirka åtta millisekunder; det är bara en räkneillustration, inte en garanti för faktisk körtid.

I en graf med 200 hörn finns åtta miljoner möjliga (i,j,k)-kombinationer. En tvådimensionell avståndsmatris har däremot bara 40 000 celler. Detta visar att kubiskt arbete kan kombineras med kvadratiskt minne.

Tidskomplexitet

Exempel för tidsanalys: Uppräkning av alla tripplar.

Tre helt nästlade loopar som oberoende går från noll till n - 1 utför kroppen n³ gånger. Det förekommer vid enkel uppräkning av tripplar och naiva varianter av vissa matrisberäkningar. Även kostnaden för Work(i, j, k) måste räknas. Mer avancerade algoritmer kan ha andra komplexitetsgränser, så exemplet är ingen allmän undre gräns.

Kontrollera looparnas gränser

Tre loopar med intervallet [0,n) gör exakt n³ anrop till innersta operationen. Är den operationen O(1) blir den totala tiden Θ(n³). Gör den i stället en ytterligare genomgång av n objekt kan tiden bli Θ(n⁴).

Floyd-Warshall utför en uppdatering för varje mellanhörn k och varje par (i,j), alltså v³ uppdateringar. Använd gärna v för antal hörn så att antalet kanter inte förväxlas med samma variabel. För stora grafer kan valet av algoritm och representation spela mycket större roll än små optimeringar i den innersta loopen.

C#

C# | Cubic.cs

for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        for (int k = 0; k < n; k++)
            Work(i, j, k);

C++

C++ | cubic.cpp

for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j)
        for (int k = 0; k < n; ++k)
            work(i, j, k);

Analys: Tre oberoende nästlade n-loopar ger O(n³) tid om Work 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 tredimensionell array.

En tredimensionell array med n × n × n positioner innehåller n³ element. Om varje element är en byte blir rådata ungefär n³ bytes utan metadata. Det skiljer sig från tre loopar, som vanligtvis bara behöver tre räknare. Om kuben är indata påverkar valet mellan totalt minne och extra minne analysen.

En kub av celler är något annat än tre loopar

En verklig n × n × n-array lagrar Θ(n³) värden. Med en byte per cell krävs ungefär en miljard databyte när n = 1 000, innan metadata. Med fyra byte per värde blir enbart innehållet cirka fyra miljarder byte.

Men en trippelloop kan använda Θ(1) extra minne för sina tre index. Floyd-Warshall lagrar normalt en v × v-avståndsmatris, alltså Θ(v²) minne trots Θ(v³) tid. Om resultaten kan behandlas ett i taget behöver programmet inte skapa en full kub. Lagra endast det som faktiskt behöver finnas kvar.

C#

C# | Cubic.cs

byte[,,] cube = new byte[n, n, n];

C++

C++ | cubic.cpp

#include <vector>
#include <cstdint>

std::vector<std::uint8_t> cube(static_cast<std::size_t>(n) * n * n);

Analys: En n × n × n-array kräver O(n³) extra minne; de tre looparna använder vanligtvis O(1) extra räknarminne.

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

Hitta kubiska flaskhalsar

Sök efter tre indata-beroende dimensioner och fråga om varje kombination måste besökas. Tre färgkanaler i en bild är en konstant dimension och gör inte en annars kvadratisk algoritm kubisk.

Kubiska algoritmer kan fungera för små, täta problem där enkelheten är värdefull. Vid större problem bör du undersöka om glesa datastrukturer, specialiserade kortaste-vägen-algoritmer eller eliminering av en dimension kan minska arbetet. En förbättrad representation kan betyda mer än en snabbare enskild instruktion.

Praktiskt exempel: avstånd mellan alla platser

Ett kartsystem kan behöva kortaste vägkostnaden mellan varje par av v platser. Floyd-Warshall prövar varje plats som möjlig mellanpunkt och uppdaterar varje start- och målpar. Det ger Θ(v³) uppdateringar enligt en vanlig modell med konstantkostnadsaritmetik, medan avståndsmatrisen kräver Θ(v²) minne. Datastrukturen är tvådimensionell, trots att beräkningen har tre nästlade loopar.

För ett litet och tätt nätverk kan detta vara en praktisk lösning. För ett stort och glest vägnät där bara en startpunkt behövs kan en annan kortaste-vägen-algoritm passa bättre. Det beror på vilka frågor programmet behöver besvara.

Vanligt misstag

Se upp: Dra inte slutsatsen att tre nästlade loopar kräver O(n³) minne. Antalet samtidigt lagrade variabler är normalt konstant om programmet inte sparar resultaten eller skapar en tredimensionell struktur.

Testa kunskaperna

Beräkna antalet anrop till loopkroppen för n = 5, 10 och 20. Uppskatta sedan minnesåtgången för en byte[,,] med samma mått.

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