Potentiel metode - Potential method

I beregningskompleksitetsteori er den potentielle metode en metode, der bruges til at analysere den amortiserede tid og rums kompleksitet af en datastruktur , et mål for dens ydeevne over sekvenser af operationer, der udjævner omkostningerne ved sjældne, men dyre operationer.

Definition af amortiseret tid

I den potentielle metode vælges en funktion that, der kortlægger datastrukturen til ikke-negative tal. Hvis S er en tilstand af datastrukturen, repræsenterer Φ ( S ) arbejde, der er registreret ("betalt for") i den amortiserede analyse, men endnu ikke udført. Således kan Φ ( S ) betragtes som beregning af mængden af potentiel energi lagret i denne tilstand. Den potentielle værdi før operationen ved initialisering af en datastruktur er defineret til at være nul. Alternativt kan Φ ( S ) betragtes som repræsenterer mængden af ​​forstyrrelse i tilstand S eller dens afstand fra en ideel tilstand.

Lad o være enhver individuel operation inden for en sekvens af operationer på nogle datastruktur, med S _før angiver tilstanden af datastrukturen inden betjening o og S _efter betegner sin tilstand efter operationen o er afsluttet. Når Φ er valgt, defineres den afskrevne driftstid o til at være

${\ displaystyle T _ {\ mathrm {amortized}} (o) = T _ {\ mathrm {actual}} (o) + C \ cdot (\ Phi (S _ {\ mathrm {after}}) - \ Phi (S _ {\ mathrm {før}})),}$

hvor C er en ikke-negativ proportionalitetskonstant (i tidsenheder), der skal forblive fast under hele analysen. Det vil sige, at den afskrevne tid defineres til at være den faktiske tid, som operationen tager plus C gange forskellen i potentiale forårsaget af operationen.

Når man studerer asymptotisk beregningskompleksitet ved hjælp af stor O-notation , er konstante faktorer irrelevante, og derfor udelades konstant C normalt.

Forholdet mellem amortiseret og faktisk tid

På trods af dets kunstige udseende tilvejebringer den samlede amortiserede tid for en sekvens af operationer en gyldig øvre grænse for det aktuelle tidspunkt for den samme sekvens af operationer.

For enhver rækkefølge af operationer skal du definere: ${\ displaystyle O = o_ {1}, o_ {2}, \ prikker, o_ {n}}$

• Den samlede amortiserede tid: ${\ displaystyle T _ {\ mathrm {amortized}} (O) = \ sum _ {i = 1} ^ {n} T _ {\ mathrm {amortized}} (o_ {i}),}$
• Den samlede faktiske tid: ${\ displaystyle T _ {\ mathrm {actual}} (O) = \ sum _ {i = 1} ^ {n} T _ {\ mathrm {actual}} (o_ {i}).}$

Derefter:

${\ displaystyle T _ {\ mathrm {amortized}} (O) = \ sum _ {i = 1} ^ {n} \ left (T _ {\ mathrm {actual}} (o_ {i}) + C \ cdot (\ Phi (S_ {i}) - \ Phi (S_ {i-1})) \ right) = T _ {\ mathrm {actual}} (O) + C \ cdot (\ Phi (S_ {n}) - \ Phi (S_ {0})),}$

hvor rækkefølgen af ​​potentielle funktionsværdier danner en teleskopserie , hvor alle andre udtryk end de indledende og endelige potentielle funktionsværdier annulleres parvis. Omarrangere dette får vi:

${\ displaystyle T _ {\ mathrm {actual}} (O) = T _ {\ mathrm {amortized}} (O) -C \ cdot (\ Phi (S_ {n}) - \ Phi (S_ {0})). }$

Siden og , , så den amortiseret tid kan anvendes til at tilvejebringe en nøjagtig øvre grænse for den faktiske tid af en sekvens af operationer, selv om amortiseret tid for en individuel operation kan variere bredt fra den faktiske tid. ${\ displaystyle \ Phi (S_ {0}) = 0}$${\ displaystyle \ Phi (S_ {n}) \ geq 0}$${\ displaystyle T _ {\ mathrm {actual}} (O) \ leq T _ {\ mathrm {amortized}} (O)}$

Amortiseret analyse af worst-case input

Typisk anvendes amortiseret analyse i kombination med en worst case antagelse om input-sekvensen. Med denne antagelse, hvis X er en type operation, der kan udføres af datastrukturen, og n er et heltal, der definerer størrelsen på den givne datastruktur (for eksempel antallet af elementer, som den indeholder), så afskrives tiden for operationer af typen X er defineret til at være den maksimale, blandt alle mulige sekvenser af operationer på datastrukturer størrelse n og alle transaktioner o _i af typen X i sekvensen, af amortiseret tid for operationen o _i .

Med denne definition kan tiden til at udføre en sekvens af operationer estimeres ved at multiplicere den afskrevne tid for hver type operation i sekvensen med antallet af operationer af den type.

Eksempler

Dynamisk matrix

Et dynamisk array er en datastruktur til vedligeholdelse af et array af elementer, der giver mulighed for både tilfældig adgang til positioner i arrayet og muligheden for at øge array-størrelsen med en. Den er tilgængelig i Java som "ArrayList" -typen og i Python som "liste" -typen.

En dynamisk matrix kan implementeres af en datastruktur, der består af en matrix A af emner med en vis længde N sammen med et tal n  ≤  N, der repræsenterer positionerne inden for arrayet, der hidtil er blevet brugt. Med denne struktur kan tilfældig adgang til det dynamiske array implementeres ved at få adgang til den samme celle i det interne array A , og når n  <  N kan en operation, der øger den dynamiske array-størrelse, implementeres simpelthen ved at inkrementere  n . Men når n  =  N , er det nødvendigt at ændre størrelse på A , og en fælles strategi for at gøre det er at fordoble størrelsen og erstatte A med en ny række med længden 2 n .

Denne struktur kan analyseres ved hjælp af den potentielle funktion:

Φ = 2 n  -  N

Da størrelsesændringsstrategien altid får A til at være mindst halvfuld, er denne potentielle funktion altid som ønsket ikke negativ.

Når en operation med forøgelsesstørrelse ikke fører til en størrelse på operation, øges Φ med 2, en konstant. Derfor kombinerer den konstante faktiske tid af operationen og den konstante stigning i potentialet for at give en konstant afskrevet tid til en operation af denne type.

Men når en operation med forøgelsesstørrelse forårsager en størrelse, falder den potentielle værdi af n til nul efter størrelsen. Tildeling af et nyt intern array A og kopiering af alle værdierne fra det gamle interne array til det nye tager O ( n ) faktisk tid, men (med et passende valg af proportionalitetskonstanten C ) annulleres dette fuldstændigt af faldet i den potentielle funktion, hvilket efterlader en konstant total afskrevet tid for operationen.

De andre operationer i datastrukturen (læsning og skrivning af array-celler uden at ændre array-størrelsen) får ikke den potentielle funktion til at ændre sig og har den samme konstante afskrivningstid som deres faktiske tid.

Derfor, med dette valg af størrelse på størrelse og potentialefunktion, viser den potentielle metode, at alle dynamiske arrayoperationer tager konstant afskrevet tid. Kombinerer dette med uligheden, der relaterer afskrevet tid og faktisk tid over sekvenser af operationer, viser dette, at enhver sekvens af n dynamisk matrixoperationer tager O ( n ) faktisk tid i værste fald på trods af, at nogle af de enkelte operationer selv kan tage en lineær tid.

Når det dynamiske array inkluderer operationer, der både reducerer array-størrelsen og øger den, skal den potentielle funktion ændres for at forhindre, at den bliver negativ. En måde at gøre dette på er at erstatte formlen ovenfor for Φ med dens absolutte værdi .

Multi-Pop stak

Overvej en stak, der understøtter følgende operationer:

• Initialiser - opret en tom stak.
• Push - tilføj et enkelt element oven på stakken, og forstør stakken med 1.
• Pop ( k ) - fjern k- elementer fra toppen af ​​stakken, hvor k ikke er mere end den aktuelle stakstørrelse

Pop ( k ) kræver O ( k ) tid, men vi vil vise, at alle operationer tager O (1) afskrevet tid.

Denne struktur kan analyseres ved hjælp af den potentielle funktion:

Φ = antal-elementer-i-stak

Dette tal er altid ikke-negativt efter behov.

En Push-operation tager konstant tid og øges Φ med 1, så dens afskrivningstid er konstant.

En popoperation tager tid O ( k ), men reducerer også Φ med k , så dens afskrivningstid er også konstant.

Dette beviser, at enhver sekvens af m- operationer tager O ( m ) faktisk tid i værste fald.

Binær tæller

Overvej en tæller repræsenteret som et binært tal og understøtter følgende operationer:

• Initialiser: Opret en tæller med værdi 0.
• Inc: tilføj 1 til tælleren.
• Læs: returner den aktuelle tællerværdi.

I dette eksempel bruger vi ikke den transdikotome maskinemodel , men kræver i stedet en tidsenhed pr. Bitoperation i inkrementet. Vi ønsker at vise, at Inc tager O (1) afskrevet tid.

Denne struktur kan analyseres ved hjælp af den potentielle funktion:

Φ = antal bit-svarende til 1 = hammingvægt (tæller)

Dette tal er altid ikke-negativt og starter med 0 efter behov.

En Inc-operation vender den mindst betydningsfulde bit . Derefter, hvis LSB blev vendt fra 1 til 0, vendes den næste bit også. Dette fortsætter indtil endelig en smule er vendt fra 0 til 1, på hvilket tidspunkt spejlvending stopper. Hvis tælleren oprindeligt slutter med k 1 bits, vender vi i alt k + 1 bits, tager den aktuelle tid k + 1 og reducerer potentialet med k −1, så den afskrevne tid er 2. Derfor er den faktiske tid til at køre m Inc-operationer er O ( m ).

Ansøgninger

Den potentielle funktionsmetode bruges ofte til at analysere Fibonacci-bunker , en form for prioritetskø , hvor fjernelse af et element tager logaritmisk afskrevet tid, og alle andre operationer tager konstant afskrevet tid. Det kan også bruges til at analysere splay træer , en selvjusterende form for binært søgetræ med logaritmisk afskrevet tid pr. Operation.

Referencer