Fakultet (O(n!))

Kort sammanfattning: Antalet möjliga ordningar växer som produkten 1 × 2 × ... × n.

Gå direkt till: Tidskomplexitet · Minneskomplexitet · Övning

Förstå tillväxten

För att ordna n olika objekt finns n val för första positionen, n-1 för den andra och sedan ett färre alternativ för varje återstående position. Produkten blir n! permutationer.

När n ökar till n + 1 multipliceras antalet permutationer med n + 1. Kvoten är alltså inte konstant som för 2ⁿ, utan blir större när n växer. Fakultet växer på sikt snabbare än varje exponentialfunktion med fast bas.

Varför antalet ordningar växer som fakultet

När n olika objekt ska ordnas finns n alternativ på första platsen, n-1 på andra, och så vidare. Multiplikationen ger n! = n × (n-1) × ... × 1. Ett nytt objekt multiplicerar antalet möjliga ordningar med n+1, vilket innebär att tillväxtfaktorn själv växer.

Fem objekt har 120 möjliga permutationer, åtta har 40 320 och tio har 3 628 800. Därför blir ren uppräkning av ordningar snabbt dyr. Exemplen omfattar brute-force-sökning efter rutter, ordningsproblem och generering av testfall i alla möjliga ordningar.

Att beräkna talet n! är däremot inte samma sak som att generera alla permutationer. En enkel produktloop använder bara n iterationer om vi bortser från kostnaden för heltal med många siffror. Var alltid tydlig med vilken uppgift som analyseras.

Ett genomräknat exempel

Fem olika objekt har 120 permutationer, sex har 720, sju har 5 040 och åtta har 40 320. Tre ytterligare objekt gör antalet ordningar 336 gånger större än för fem objekt.

Tre objekt ger sex permutationer

Börja med [A, B, C]. Första platsen kan få A, B eller C. Därefter finns två val kvar och till sist ett. Bladen är ABC, ACB, BAC, BCA, CAB och CBA: 3 × 2 × 1 = 6.

Om vi lägger till D finns 24 ordningar och med E hela 120. En lösning som provar varje ordning måste åtminstone utvärdera det antalet kandidater, och kostnaden för att kopiera eller poängsätta varje permutation tillkommer. Att byta element på plats är oftast mer minnessnålt än att lagra samtliga resultat.

Tidskomplexitet

Exempel för tidsanalys: Uppräkning av permutationer.

Exemplet med byte och rekursion väljer ett värde för varje position tills en fullständig permutation bildas. Det besöker n! löv. Om ProcessPermutation kostar konstant arbete kan traverseringen beskrivas som Θ(n!) enligt denna modell. Om varje resultat måste skrivas ut eller kopieras behövs Θ(n·n!) arbete för utdata. Dubbletter i indatan ger upprepade ordningar om de inte hanteras separat.

Räkna även arbetet per permutation

Algoritmen väljer i varje rekursionsnivå ett av de återstående elementen och byter tillbaka efter anropet. Den besöker n! blad. Om bladfunktionen kostar O(1) blir det Θ(n!) arbete i rekursionens noder och byten för n minst två.

Om varje full permutation behöver kopieras eller utvärderas över alla n positioner blir totalen Θ(n·n!). Även utskrift av samtliga permutationer kräver minst Ω(n·n!) arbete. Utan återställande byte riskerar de följande rekursionsgrenarna att börja med fel arraytillstånd.

C#

C# | Factorial.cs

void Permute(int pos, int[] a)
{
    if (pos == a.Length) { ProcessPermutation(a); return; }
    for (int i = pos; i < a.Length; i++)
    {
        (a[pos], a[i]) = (a[i], a[pos]);
        Permute(pos + 1, a);
        (a[pos], a[i]) = (a[i], a[pos]);
    }
}

C++

C++ | factorial.cpp

#include <vector>
#include <utility>

void permute(int pos, std::vector<int>& a) {
    if (pos == static_cast<int>(a.size())) { processPermutation(a); return; }
    for (int i = pos; i < static_cast<int>(a.size()); ++i) {
        std::swap(a[pos], a[i]);
        permute(pos + 1, a);
        std::swap(a[pos], a[i]);
    }
}

Analys: Permutationstraverseringen besöker n! löv och har Θ(n!) arbete om varje färdigt resultat behandlas i O(1). Om varje permutation kopieras blir tiden Θ(n·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: En markör per permutation.

En generator som arbetar på plats kan återanvända indataarrayen och behöver högst n rekursiva anropsramar, alltså O(n) extra stackminne. En markör per permutation tar Θ(n!) celler, medan alla kompletta permutationer av längd n tar Θ(n·n!) elementceller. Exemplet använder avsiktligt en byte per permutation som minnesexempel, inte för att beskriva generatorns förbrukning.

Uppräkning kräver inte fakultetsmycket minne

En generator som byter element i samma array behåller den aktuella ordningen och högst n+1 aktiva anrop. Extra stackminne är Θ(n); om indataarrayen räknas med är även den aktuella arbetsrepresentationen Θ(n).

Om du däremot sparar en konstant stor markering för var och en av de n! permutationerna behövs Θ(n!) minne. Att lagra varje hel permutation med n värden kräver Θ(n·n!) celler. Redan 10! överstiger tre miljoner; att skapa och spara alla ordningar blir snabbt opraktiskt.

C#

C# | Factorial.cs

// Allocate one byte of metadata per permutation.
// For sufficiently small n only:
byte[] flags = new byte[Factorial(n)];

C++

C++ | factorial.cpp

#include <vector>
#include <cstdint>

// One byte per permutation illustrates O(n!) space (small n only).
std::vector<std::uint8_t> flags(factorial(n));

Analys: En markör per permutation kräver Θ(n!) minne; om alla n element kopieras i varje permutation krävs Θ(n·n!). Generering på plats har O(n) stack.

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

När ska man faktiskt räkna upp alla ordningar?

Fakultetsarbete är rimligt om användaren uttryckligen vill ha varje unik permutation. Om målet bara är en bra ordning bör man först undersöka dynamisk programmering, begränsningar, branch-and-bound eller problemets särskilda struktur.

Vissa ordningsproblem innehåller symmetrier eller identiska element, vilket minskar antalet unika permutationer. En rekursiv lösning är inte automatiskt O(n!); analysera vilka grenar som faktiskt skapas och om upprepade tillstånd kan återanvändas. Skilj också mellan att räkna antalet arrangemang och att generera dem.

Praktiskt exempel: ordna leveransstopp

I ett dispatch-spel kan ett fordon få åtta olika leveransstopp. Att prova varje ordning innebär 8! = 40 320 rutter, redan innan själva ruttkostnaden beräknas. Med tio stopp blir det 10! = 3 628 800 kandidater. Om varje rutt kräver att tio avstånd summeras tillkommer arbete per kandidat, så den totala tiden blir större än bara antalet permutationer.

För små problem kan uttömmande sökning användas som kontroll av korrekthet för en snabbare heuristik. Vid större problem kan dynamisk programmering, branch-and-bound eller approximationsmetoder passa bättre. En rekursiv lösning är inte automatiskt fakultetskomplex; räkna grenar, beskärning och arbete per kandidat.

Vanligt misstag

Se upp: Skilj mellan att generera permutationer, att beräkna deras antal matematiskt och att söka en lämplig permutation. Att n! ordningar existerar betyder inte att alla problem måste undersöka samtliga.

Testa kunskaperna

Skriv upp de sex permutationerna av tre olika värden. Jämför sedan antal ordningar för sex och sju värden och avgör om alla resultat verkligen behöver lagras.

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