Exponentiell (O(2ⁿ))

Kort sammanfattning: Antalet möjligheter fördubblas när ett nytt oberoende ja/nej-val läggs till.

Gå direkt till: Tidskomplexitet · Minneskomplexitet · Övning

Förstå tillväxten

För varje element väljer man om det ska ingå i en delmängd eller inte. Varje nytt element fördubblar antalet kombinationer. Att undersöka alla kombinationer är därför något helt annat än att läsa listan en gång.

Med n oberoende binära val finns exakt 2ⁿ löv i beslutsträdet. När n ökar med ett fördubblas antalet: 2^(n+1) = 2 × 2ⁿ. Tillväxten blir på sikt snabbare än alla polynom med fast exponent.

Två val per objekt

För varje objekt i en delmängd kan du välja ta med eller utelämna. Varje nytt objekt fördubblar antalet kombinationer. Ett fullt binärt beslutsträd med djup n har 2ⁿ blad och 2^(n+1)-1 noder. Att göra konstant arbete per nod ger därför Θ(2ⁿ) tid.

Vid 20 objekt finns 1 048 576 delmängder; vid 30 över en miljard. Tillväxten beror på antalet oberoende beslut, inte bara hur många byte varje objekt upptar. Om problemet tillåter att grenar kapas eller att upprepade tillstånd sammanfattas kan en bättre algoritm undvika att besöka alla alternativ.

Rekursion i sig innebär inte exponentiell tid. En funktion med ett anrop per nivå kan vara linjär, medan två anrop med överlappande problem ibland kan optimeras med memoisering. Analysera antalet utförda grenar eller unika tillstånd.

Ett genomräknat exempel

Vid n = 10 finns 1 024 delmängder, vid n = 20 drygt en miljon och vid n = 30 mer än en miljard. Tio ytterligare binära beslut multiplicerar antalet med 1 024.

Tre val ger åtta vägar

Med objekten A, B och C kan en delmängd beskrivas med tre bitar där 1 betyder ta med. De möjliga valen är 000, 001, 010, 011, 100, 101, 110 och 111. Totalt finns åtta blad i beslutsträdet.

Om D läggs till får varje tidigare väg två varianter och antalet fördubblas till sexton. En djupet-först-genomgång besöker ett val i taget och behöver inte lagra alla tidigare val. Det är skillnaden mellan att besöka och att spara alla delmängder.

Tidskomplexitet

Exempel för tidsanalys: Alla inkluderings- och exkluderingsval.

Den rekursiva include/exclude-funktionen följer två grenar för varje element och når 2ⁿ löv. Om behandlingen av ett löv kostar O(1) blir tiden Θ(2ⁿ). Om varje delmängd skrivs ut eller kopieras kan det kosta O(n) per löv, alltså Θ(n·2ⁿ) för resultatmaterialet. Beskärning kan minska arbetet på vissa indata, men det ändrar inte det fullständiga trädets storlek.

Arbete per blad spelar roll

Om ProcessChoice() kostar O(1) och alla grenar besöks blir tiden Θ(2ⁿ). Om funktionen däremot kopierar en hel längd-n-representation för varje blad kan tiden bli Θ(n·2ⁿ). Antalet blad räcker alltså inte för en fullständig analys.

En backtracking-algoritm kan avsluta när den hittar en lösning, vilket ibland går fort. Om ingen giltig lösning finns kan den ändå behöva söka igenom alla grenar. Beskriv därför vilken beskärning som är garanterad innan du påstår en lägre övre gräns.

C#

C# | Exponential.cs

void Enumerate(int index, int n)
{
    if (index == n) { ProcessChoice(); return; }
    Enumerate(index + 1, n); // exclude
    Enumerate(index + 1, n); // include
}

C++

C++ | exponential.cpp

void enumerate(int index, int n) {
    if (index == n) { processChoice(); return; }
    enumerate(index + 1, n); // exclude
    enumerate(index + 1, n); // include
}

Analys: Det finns 2ⁿ löv. Traversering tar O(2ⁿ) tid om varje löv behandlas i O(1). Rekursionsstacken är bara O(n).

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

Minneskomplexitet

Exempel för minnesanalys: Sparade delmängder.

Djupet-först-sökning behåller bara n beslut på stacken samtidigt och använder därför O(n) stackminne, inte O(2ⁿ). Om en markör sparas för varje delmängd behövs Θ(2ⁿ) minne. Om alla delmängder lagras som listor av sina medlemmar blir summan Θ(n·2ⁿ), eftersom varje av de n elementen finns i hälften av delmängderna. Skillnaden spelar stor roll om alla resultat verkligen lagras.

Linjär stack, exponentiella resultat

En djupet-först-enumerering har högst n+1 aktiva rekursionsramar samtidigt och kan hålla det aktuella valet i n booleska värden. Den använder då Θ(n) extra minne trots exponentiell tid.

Om ett enda booleskt resultat sparas för varje delmängd krävs Θ(2ⁿ) celler. Om varje delmängd lagras som en full array med n platser blir utrymmet Θ(n·2ⁿ). Räknar vi bara lagrade medlemmar över alla delmängder blir totalsumman n·2^(n-1), fortfarande Θ(n·2ⁿ). Skilj på strömning, sammanfattning och full lagring.

C#

C# | Exponential.cs

// n must be small (0 <= n < 30) for this demonstration.
// One flag per subset: 2^n boolean entries.
bool[] flags = new bool[1 << n];

C++

C++ | exponential.cpp

#include <vector>

// n recursive decisions: O(n) stack; 2^n stored flags: O(2^n).
std::vector<bool> flags(std::size_t{1} << n); // only small n

Analys: En markör per delmängd kräver minst Ω(2ⁿ) minne; att lagra varje delmängds medlemmar tar Θ(n·2ⁿ), inte bara O(2ⁿ).

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

Undvik exponentiell sökning när det går

Om du ser oberoende ja/nej-val, fråga om samma delproblem beräknas flera gånger. Memoisering och dynamisk programmering kan ibland återanvända resultat. Begränsningar kan göra att stora delar av beslutsträdet aldrig behöver besökas.

Men om uppgiften uttryckligen kräver alla delmängder finns exponentiellt många utdata, och själva utskriften tar exponentiell tid. Blanda inte ihop O(2ⁿ) med O(n²): i det ena uttrycket ligger indatastorleken i exponenten.

Praktiskt exempel: testa kombinationer av funktioner

En spelversion kan innehålla tio oberoende av/på-inställningar. Att testa alla kombinationer kräver 2^10 = 1 024 testfall. Fem ytterligare inställningar ger 2^15 = 32 768, alltså 32 gånger så många. Ett testverktyg måste räkna både antalet kombinationer och körtiden för varje enskilt test.

Om målet är att upptäcka vanliga samspel mellan funktioner kan parvis testning eller utvalda scenarier vara praktiska, men de bevisar inte att varje fullständig kombination fungerar. Om kravet verkligen är uttömmande testning finns ett exponentiellt antal fall som måste hanteras.

Vanligt misstag

Se upp: Anta inte att minnet är O(2ⁿ) bara för att tiden är exponentiell. Att faktiskt lagra medlemmarna i alla delmängder tar Θ(n·2ⁿ) celler, inte bara O(2ⁿ).

Testa kunskaperna

För fyra element: skriv upp de sexton include/exclude-valen. Räkna maximal rekursionsnivå och jämför med att lagra alla sexton resultaten.

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