Potentiell metod

I beräkningskomplexitetsteorin är den potentiella metoden en metod som används för att analysera den amorterade tids- och rymdkomplexiteten hos en datastruktur , ett mått på dess prestanda över sekvenser av operationer som jämnar ut kostnaden för sällsynta men dyra operationer.

Definition av amorterad tid

I potentialmetoden väljs en funktion Φ som mappar datastrukturens tillstånd till icke-negativa tal. Om S är ett tillstånd i datastrukturen, representerar Φ( S ) arbete som har redovisats ("betalt") i den avskrivna analysen men ännu inte utförts. Således kan Φ( S ) ses som en beräkning av mängden potentiell energi lagrad i det tillståndet. Potentialvärdet före operationen att initiera en datastruktur definieras till noll. Alternativt kan Φ( S ) tänkas representera mängden störning i tillstånd S eller dess avstånd från ett idealiskt tillstånd.

Låt o vara vilken enskild operation som helst inom en sekvens av operationer på någon datastruktur, där S _före betecknar tillståndet för datastrukturen före operation o och S _efter att beteckna dess tillstånd efter operation o har slutförts. När Φ väl har valts, definieras den amorterade tiden för operation o vara

$T_{\mathrm {amortiserat} }(o)=T_{\mathrm {faktisk} }(o)+C\cdot (\Phi (S_{\mathrm {after} })-\Phi (S_{\ mathrm {före} })),$

där C är en icke-negativ proportionalitetskonstant (i tidsenheter) som måste förbli fixerad under hela analysen. Det vill säga, den avskrivna tiden definieras som den faktiska tid som operationen tar plus C gånger skillnaden i potential orsakad av operationen.

När man studerar asymptotisk beräkningskomplexitet med hjälp av big O-notation är konstanta faktorer irrelevanta och därför utelämnas vanligtvis konstanten C.

Förhållandet mellan avskriven och faktisk tid

Trots dess artificiella utseende ger den totala amorterade tiden för en operationssekvens en giltig övre gräns för den faktiska tiden för samma operationssekvens.

För alla operationssekvenser ${\displaystyle O=o_{1},o_{2},\dots ,o_{n}} ,$ definiera:

• Den totala amorterade tiden: $T_{\mathrm {amortized} } (O)=\summa _{i=1}^{n}T_{\mathrm {amorterad} }(o_{i}),$
• Den totala faktiska tiden: $T_{\mathrm {faktisk} }(O)=\summa _{i=1}^{n}T_{\mathrm {faktisk} }(o_{i}).$

Sedan:

$T_{\mathrm {amortiserad} }(O)=\summa _{i=1} ^{n}\left(T_{\mathrm {faktisk}}(o_{i})+C\cdot (\Phi (S_{i})-\Phi (S_{i-1}))\right)= T_{\mathrm {faktisk} }(O)+C\cdot (\Phi (S_{n})-\Phi (S_{0})),$

där sekvensen av potentiella funktionsvärden bildar en teleskopisk serie där alla andra termer än de initiala och slutliga potentiella funktionsvärdena upphäver i par. När vi ordnar om detta får vi:

$T_{\mathrm {faktisk} }(O)=T_{\mathrm {amortiserad} }(O)-C\cdot (\Phi (S_{n})-\Phi (S_{0})).$

Eftersom $\Phi (S_{0})=0$ och $\Phi (S_{n})\geq 0$ , ${\displaystyle T_{\mathrm {faktisk} }(O)\leq T_{\mathrm {amortiserad} }(O)} ,$ alltså den amorterade tiden kan användas för att ge en exakt övre gräns för den faktiska tiden för en sekvens av operationer, även om den amorterade tiden för en enskild operation kan variera kraftigt från dess faktiska tid.

Amorterad analys av värsta tänkbara indata

Normalt används amortiserad analys i kombination med ett värsta fall antagande om indatasekvensen. Med detta antagande, om X är en typ av operation som kan utföras av datastrukturen, och n är ett heltal som definierar storleken på den givna datastrukturen (till exempel antalet objekt som den innehåller), då den amorterade tiden för operationer av typ oi _X definieras som den maximala, bland alla möjliga operationssekvenser på datastrukturer av storlek n och alla operationer _oi av typ X inom sekvensen, av den amorterade tiden för operation .

Med denna definition kan tiden för att utföra en sekvens av operationer uppskattas genom att multiplicera den amorterade tiden för varje typ av operation i sekvensen med antalet operationer av den typen.

Exempel

Dynamisk array

En dynamisk array är en datastruktur för att upprätthålla en array av objekt, vilket möjliggör både slumpmässig åtkomst till positioner inom arrayen och möjligheten att öka arraystorleken med en. Den är tillgänglig i Java som typen "ArrayList" och i Python som typen "list".

En dynamisk array kan implementeras av en datastruktur bestående av en array A av objekt, av någon längd N , tillsammans med ett nummer n < N representerande positionerna inom arrayen som hittills har använts. Med denna struktur kan slumpmässiga åtkomster till den dynamiska arrayen implementeras genom åtkomst till samma cell i den interna arrayen A , och när n < N kan en operation som ökar den dynamiska arraystorleken implementeras helt enkelt genom att öka n . Men när n = N är det nödvändigt att ändra storlek på A , och en vanlig strategi för att göra det är att fördubbla dess storlek, och ersätta A med en ny array med längden 2 n .

Denna struktur kan analyseras med hjälp av den potentiella funktionen:

Φ = 2 n − N

Eftersom storleksändringsstrategin alltid gör att A är minst halvfullt, är denna potentiella funktion alltid icke-negativ, enligt önskemål.

När en ökningsoperation inte leder till en storleksändringsoperation, ökar Φ med 2, en konstant. Därför kombineras den konstanta faktiska tiden för operationen och den konstanta ökningen i potential för att ge en konstant amorterad tid för en operation av denna typ.

Men när en ökning av storleken orsakar en storleksändring, minskar det potentiella värdet för Φ till noll efter storleksändringen. Att allokera en ny intern array A och kopiera alla värden från den gamla interna arrayen till den nya tar O( n ) faktisk tid, men (med ett lämpligt val av proportionalitetskonstanten C ) upphävs detta helt av minskningen i den potentiella funktionen, vilket återigen lämnar en konstant total amorterad tid för operationen.

De andra operationerna i datastrukturen (läsa och skriva arrayceller utan att ändra arraystorleken) orsakar inte att den potentiella funktionen ändras och har samma konstanta amorterade tid som deras faktiska tid.

Därför, med detta val av storleksändringsstrategi och potentiell funktion, visar den potentiella metoden att alla dynamiska arrayoperationer tar konstant amorterad tid. Genom att kombinera detta med olikheten som relaterar till amorterad tid och faktisk tid över sekvenser av operationer, visar detta att varje sekvens av n dynamiska array-operationer tar O( n ) faktisk tid i värsta fall, trots att vissa av de individuella operationerna själva kan ta en linjär tidsperiod.

När den dynamiska arrayen inkluderar operationer som minskar arraystorleken såväl som ökar den, måste potentialfunktionen modifieras för att förhindra att den blir negativ. Ett sätt att göra detta är att ersätta formeln ovan för Φ med dess absoluta värde .

Multi-pop stack

Tänk på en stack som stöder följande operationer:

• Initiera - skapa en tom stack.
• Push - lägg till ett enda element ovanpå stapeln, förstora stapeln med 1.
• Pop( k ) - ta bort k element från toppen av stapeln, där k inte är mer än den aktuella stapelstorleken

Pop( k ) kräver O( k ) tid, men vi vill visa att alla operationer tar O(1) amorterad tid.

Denna struktur kan analyseras med hjälp av den potentiella funktionen:

Φ = antal element-i-stack

Detta nummer är alltid icke-negativt vid behov.

En push-operation tar konstant tid och ökar Φ med 1, så dess amorterade tid är konstant.

En Pop-operation tar tid O( k ) men minskar också Φ med k , så dess amorterade tid är också konstant.

Detta bevisar att varje sekvens av m operationer tar O( m ) faktisk tid i värsta fall.

Binär räknare

Betrakta en räknare som representeras som ett binärt tal och som stöder följande operationer:

• Initiera: skapa en räknare med värdet 0.
• Inc.: lägg till 1 i räknaren.
• Läs: returnera det aktuella räknarvärdet.

För det här exemplet använder vi inte den transdikotoma maskinmodellen utan kräver istället en tidsenhet per bitoperation i inkrementet. Vi vill visa att Inc tar O(1) amorterad tid.

Denna struktur kan analyseras med hjälp av den potentiella funktionen:

Φ = antal-bitar-lika-till-1 = hammingvikt (räknare)

Detta nummer är alltid icke-negativt och börjar med 0 efter behov.

En Inc-operation vänder den minst signifikanta biten . Sedan, om LSB vänts från 1 till 0, så vänds även nästa bit. Detta fortsätter tills en bit till slut vänds från 0 till 1, vid vilken punkt vändningen slutar. Om räknaren initialt slutar på k 1 bitar, vänder vi totalt k +1 bitar, tar den faktiska tiden k +1 och minskar potentialen med k −1, så den amorterade tiden är 2. Därför är den faktiska tiden för att köra m Inc verksamhet är O( m ).

Ansökningar

Den potentiella funktionsmetoden används vanligtvis för att analysera Fibonacci-högar , en form av prioritetskö där borttagning av ett objekt tar logaritmisk amorterad tid, och alla andra operationer tar konstant amorterad tid. Den kan också användas för att analysera splay trees , en självjusterande form av binärt sökträd med logaritmisk amorterad tid per operation.