Potensiell metode - Potential method

I beregningskompleksitetsteori er den potensielle metoden en metode som brukes til å analysere amortisert tid og romkompleksitet i en datastruktur , et mål på ytelsen over operasjonssekvenser som jevner ut kostnadene ved sjeldne, men dyre operasjoner.

Definisjon av amortisert tid

I den potensielle metoden velges en funksjon Φ som kartlegger tilstandene til datastrukturen til ikke-negative tall. Hvis S er en tilstand av datastrukturen, representerer Φ ( S ) arbeid som er regnskapsført ("betalt for") i amortisert analyse, men som ennå ikke er utført. Dermed kan Φ ( S ) betraktes som beregning av mengden potensiell energi lagret i den tilstanden. Den potensielle verdien før operasjonen med å initialisere en datastruktur er definert til å være null. Alternativt kan Φ ( S ) betraktes som å representere mengden forstyrrelse i tilstand S eller dens avstand fra en ideell tilstand.

La o være hvilken som helst individuell operasjon innenfor en sekvens av operasjoner på en datastruktur, med S _før som angir tilstanden av datastrukturen før operasjon o og S _etter som betegner dens tilstand etter operasjon o er fullført. Når Φ er valgt, defineres den amortiserte tiden for drift o til å være

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

der C er en ikke-negativ proporsjonalitetskonstant (i tidsenheter) som må forbli fast gjennom hele analysen. Det vil si at den amortiserte tiden er definert til å være den faktiske tiden det tar operasjonen pluss C ganger differansen i potensial forårsaket av operasjonen.

Når man studerer asymptotisk beregningskompleksitet ved å bruke stor O-notasjon , er konstante faktorer irrelevante, og konstant C blir derfor utelatt.

Forholdet mellom amortisert og faktisk tid

Til tross for det kunstige utseendet gir den totale amortiserte tiden for en sekvens av operasjoner en gyldig øvre grense på det faktiske tidspunktet for samme sekvens av operasjoner.

For enhver rekkefølge av operasjoner , definer: ${\ displaystyle O = o_ {1}, o_ {2}, \ prikker, o_ {n}}$

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

Deretter:

${\ 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})),}$

der sekvensen av potensielle funksjonsverdier danner en teleskopserie der alle andre begreper enn de innledende og endelige potensielle funksjonsverdiene avbrytes parvis. Omorganisere dette får vi:

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

Siden og , slik at den amortiserte tiden kan brukes til å gi en nøyaktig øvre grense for det faktiske tidspunktet for en sekvens av operasjoner, selv om den amortiserte tiden for en individuell operasjon kan variere mye fra den faktiske tiden. ${\ displaystyle \ Phi (S_ {0}) = 0}$${\ displaystyle \ Phi (S_ {n}) \ geq 0}$${\ displaystyle T _ {\ mathrm {actual}} (O) \ leq T _ {\ mathrm {amortized}} (O)}$

Amortisert analyse av worst-case innspill

Vanligvis brukes amortisert analyse i kombinasjon med en worst case antagelse om inngangssekvensen. Med denne antagelsen, hvis X er en type operasjon som kan utføres av datastrukturen, og n er et heltall som definerer størrelsen på den gitte datastrukturen (for eksempel antall elementer den inneholder), så blir amortisert tid for operasjoner av type X er definert som det maksimale, blant alle mulige sekvenser av operasjoner på datastrukturer av størrelse n og alle operasjoner o _i av type X i sekvensen, av den amortiserte tiden for operasjon o _i .

Med denne definisjonen kan tiden for å utføre en sekvens av operasjoner estimeres ved å multiplisere den amortiserte tiden for hver type operasjon i sekvensen med antall operasjoner av den typen.

Eksempler

Dynamisk matrise

En dynamisk matrise er en datastruktur for å opprettholde en rekke elementer, slik at både tilfeldig tilgang til posisjoner i matrisen og muligheten til å øke matrisestørrelsen med en. Den er tilgjengelig i Java som "ArrayList" -typen og i Python som "listetype".

En dynamisk matrise kan implementeres av en datastruktur som består av en matrise A av elementer, med en viss lengde N , sammen med et tall n  ≤  N som representerer posisjonene i matrisen som hittil har blitt brukt. Med denne strukturen kan tilfeldige tilganger til den dynamiske matrisen implementeres ved å få tilgang til samme celle i den interne matrisen A , og når n  <  N kan en operasjon som øker den dynamiske matrisestørrelsen implementeres ganske enkelt ved å inkrementere  n . Imidlertid, når n  =  N , er det nødvendig å endre størrelse på A , og en vanlig strategi for å gjøre det er å doble størrelsen, og erstatte A med en ny matrise med lengden 2 n .

Denne strukturen kan analyseres ved hjelp av den potensielle funksjonen:

Φ = 2 n  -  N

Siden størrelsesendringsstrategien alltid fører til at A er minst halvfull, er denne potensielle funksjonen alltid ikke-negativ, som ønsket.

Når en økningsstørrelsesoperasjon ikke fører til en endring av størrelse, øker Φ med 2, en konstant. Derfor kombinerer den konstante faktiske tiden for operasjonen og den konstante økningen i potensial for å gi en konstant amortisert tid for en operasjon av denne typen.

Imidlertid, når en økning i størrelse øker størrelsen, reduseres den potensielle verdien av n til null etter størrelsen. Tildeling av en ny intern matrise A og kopiering av alle verdiene fra den gamle interne matrisen til den nye tar O ( n ) faktisk tid, men (med et passende valg av proporsjonalitetskonstanten C ) blir dette fullstendig kansellert av reduksjonen i den potensielle funksjonen, og igjen igjen en konstant total amortisert tid for operasjonen.

De andre operasjonene i datastrukturen (lesing og skriving av matrixceller uten å endre matrisestørrelsen) fører ikke til at den potensielle funksjonen endres og har samme konstant amortiserte tid som deres faktiske tid.

Derfor, med dette valget av størrelsesendringsstrategi og potensiell funksjon, viser den potensielle metoden at alle dynamiske arrayoperasjoner tar konstant amortisert tid. Kombinerer dette med ulikheten knyttet til amortisert tid og faktisk tid over sekvenser av operasjoner, viser dette at en hvilken som helst sekvens av n dynamiske arrayoperasjoner tar O ( n ) faktisk tid i verste fall, til tross for at noen av de enkelte operasjonene selv kan ta en lineær tid.

Når den dynamiske matrisen inkluderer operasjoner som reduserer matrisestørrelsen og øker den, må den potensielle funksjonen endres for å forhindre at den blir negativ. En måte å gjøre dette på er å erstatte formelen ovenfor for Φ med sin absolutte verdi .

Multi-Pop Stack

Vurder en stabel som støtter følgende operasjoner:

• Initialiser - opprett en tom stabel.
• Trykk - legg til et enkelt element på toppen av bunken, forstørr bunken med 1.
• Pop ( k ) - fjern k- elementer fra toppen av bunken, der k ikke er mer enn gjeldende stakkstørrelse

Pop ( k ) krever O ( k ) tid, men vi ønsker å vise at alle operasjoner tar O (1) amortisert tid.

Denne strukturen kan analyseres ved hjelp av den potensielle funksjonen:

Φ = antall elementer i stabelen

Dette tallet er alltid ikke-negativt, etter behov.

En push-operasjon tar konstant tid og øker Φ med 1, så den amortiserte tiden er konstant.

En popoperasjon tar tid O ( k ), men reduserer også Φ med k , så den amortiserte tiden er også konstant.

Dette beviser at enhver sekvens av m- operasjoner tar O ( m ) faktisk tid i verste fall.

Binær teller

Betrakt en teller som er representert som et binært tall og støtter følgende operasjoner:

• Initialiser: Opprett en teller med verdien 0.
• Inc: legg 1 til disken.
• Les: returner gjeldende tellerverdi.

For dette eksemplet bruker vi ikke den transdikotome maskinmodellen , men krever i stedet en tidsenhet per bitoperasjon i trinnet . Vi ønsker å vise at Inc tar O (1) amortisert tid.

Denne strukturen kan analyseres ved hjelp av den potensielle funksjonen:

Φ = antall-bits-lik-til-1 = hammingvekt (teller)

Dette tallet er alltid ikke-negativt og starter med 0, etter behov.

En Inc-operasjon vender den minst betydningsfulle biten . Så, hvis LSB ble snudd fra 1 til 0, blir den neste biten også snudd. Dette fortsetter til slutt endres litt fra 0 til 1, og da stopper flippen. Hvis telleren i utgangspunktet ender med k 1 bits, snur vi totalt k + 1 bits, tar faktisk tid k +1 og reduserer potensialet med k −1, så den amortiserte tiden er 2. Derfor er den faktiske tiden for å kjøre m Inc-operasjoner er O ( m ).

applikasjoner

Den potensielle funksjonsmetoden brukes ofte til å analysere Fibonacci-dynger , en form for prioritetskø der fjerning av et element tar logaritmisk amortisert tid, og alle andre operasjoner tar konstant amortisert tid. Det kan også brukes til å analysere flekker , en selvjusterende form for binært søketre med logaritmisk amortisert tid per operasjon.

Referanser