N10

10.

Amortizációs költségelemzés

Tekintsünk egy

u1 ; . . . ; um muveletsort. ˝ A muveletsor ˝ futási idejének kifejezésére több mód használatos. 1. Külön-külön minden egyes muvelet ˝ futási idejét kifejezzük és összegezzük. 2. A teljes muveletsor ˝ összesített költségét számítjuk, de az egyes muveletekét ˝ nem. 3. A muveletekre ˝ átlagolt T (n)/m költséget számítjuk. Ezt az egyes muveletek ˝ átlagolt költségének nevezzük. A legrosszabb esetre az 1. módszer gyakran nem adekvát, mert nem éles.

10.1.

Összesítéses elemzés

Összesítéses elemzésnél minden n-re megmutatjuk, hogy n elemu˝ muveletsor ˝ legrosszabb esetben összesen T (n) ideig tart. Tehát a muveletenkénti ˝ átlagos vagy amortizált költség T (n)/n. Verem muvelek ˝ Vezessünk be a Verem adattípus K IVESZ (V,K) új muveletét. ˝ Értékhalmaz: Verem = {ha1 , . . . , an i : ai ∈ E, i = 1, . . . , n, n ≥ 0} Muveletek: ˝

V : Verem, x : E

{V = ha1 , . . . , an i}

VeremBe(V, x)

{V = ha1 , . . . , an , xi}

{V = ha1 , . . . , an i ∧ n > 0}

VeremBol(V, x)

{V = ha1 , . . . , an−1 i ∧ x = an }

{V = V }

Urese(V )

{Urese = (Pre(V ) = hi)}

{V = ha1 , . . . , an i ∧ n > 0}

Torol(V )

{V = ha1 , . . . , an−1 i}

{V = ha1 , . . . , an i ∧ n > k}

Kivesz(V, k)

{V = ha1 , . . . , an−k i}

{V = ha1 , . . . , an i ∧ n ≤ k}

Kivesz(V, k)

{V = hi}

A K IVESZ (V, K ) muvelet ˝ megvalósítható TOROL (V) muvelettel: ˝ while (k>0) and not Urese(V) do Begin Torol(V); k:=k-1 end;

Az 1. módszer szerint a költség legrosszabb esetben O(n2 ), mivel a K IVESZ muvelet ˝ legrosszabb esetben n elemet vesz ki, aminek költsége O(n). Az összesített költség azonban O(n), mert minden elem a verembe egyszer kerülhet be és egyszer ki. Tehát az átlagolt költség O(n)/n = O(1). Bináris számláló növelése Tekintsük az A[0..k − 1] bitvektort, ami egy szám 2-es számrendszerbeli leírása, nevezetesen i k ˝ eljárást x = ∑k−1 i=0 A[i]2 . Legyen kezdetben x = 0, azaz A[i] = 0, i = 0, . . . k − 1. Az x := x + 1 eggyel (mod 2 ) való növelésre a következo használjuk.

N OVEL(A) Begin i:=0; while (i
A[i] := 1 end;

˝ kapjuk. A legrosszabb esetben, amikor minden bit 1-es, a muvelet Az 1. módszert alkalmazva a következot ˝ O(k) ideig tart, tehet a muveletsor ˝ költsége legrosszabb esetben O(n k). ˝ nem mindegyik változtatja mind a k bitet. Látszik, hogy az A[0] bit mindig Élesíthetjük a korlátot, ha észrevesszük, hogy az n N OVEL muveletb ˝ ol

1

megváltozik, Az A[1] bit minden második muveletben, ˝ tehát bn/2c-ször. Általánosan, i = 0, 1, . . . , k − 1 esetén az A[i] bit megváltozásainak száma bn/2i c. Ha i > k esetben nem változik bit. Tehát a bit-változások száma: blg nc j

∑

i=0

nk 2i

∞

<

1 = 2n i 2 i=0

n∑

˝ álló muveletsor Tehát n N OVEL muveletb ˝ ol ˝ összesített költség, ha 0-val indulunk O(n), így az amortizált költség O(n)/n = O(1).

10.2.

Könyvelési módszer

A könyvelési módszer esetén különbözo˝ amortizált költséget számítunk ez egyes muveletekre, ˝ megengedve azt is, hogy egyes muveletek ˝ esetén a tényleges költségnél többet, másoknál kevesebbet számlázzunk. Az az összeg, amit egy adott muveletre ˝ felszámítunk, a muvelet ˝ amortizációs költsége. Ha felso˝ korlátot akarunk adni (a legrosszabb esetre), akkor az amortizációs összköltség a tényleges összköltség felso˝ korlátja kell legyen minden n-re. n

n

i=1

i=1

∑ cbi ≥ ∑ ci

(1)

Verem muvelek ˝ A tényleges muveleti ˝ költségek: V EREMBE 1 V EREMBOL 1 K IVESZ min(k, |V |) ˝ A következo˝ amortizációs költségekre teljesül az (1) egyenlotlenség: V EREMBE 2 V EREMBOL 0 K IVESZ 0 Tehát a teljes költség O(n). Bináris számláló A tényleges költség annyi, ahány bitet megváltoztat a muvelet. ˝ ˝ Számítsunk 2 amortizációs költséget, ha egy bitet 1-re állítunk be. Ekkor szintén teljesül az (1) egyenlotlenség, tehát az összköltség O(n).

10.3.

Potenciál módszer

Feltételezzük, hogy minden muvelet ˝ ugyanazon D adatszerkezeten hajt végre muveletet. ˝ A kezdeti helyzete D0 , az i-edik muvelet ˝ végrehajtása után Di . ˝ kifizetett munkát nem az adatszerkezet egyes elemeihez rendeli, hanem mint Az amortizációs költségelemzés potenciál módszere az elore ˝ "potenciális energiát", röviden potenciált, ami a jövobeni muveletek ˝ kifizetésére használható. Ezt a potenciált az adatszerkezet egészéhez rendeljük hozzá. A Φ potenciál függvény a Di adatszerkezethez egy Φ(Di ) valós számot rendel, ami a Di adatszerkezethez rendelt potenciál. Az i-edik muvelet ˝ cbi amortizációs költségét a Φ potenciálfüggvényre vonatkozóan a

cbi = ci + Φ(Di ) − Φ(Di−1 ) .

(2)

egyenlettel definiáljuk. a teljes amortizációs költséget a n

∑ cbi

n

=

i=1

∑ (ci + Φ(Di ) − Φ(Di−1 ))

i=1 n

=

∑ ci + Φ(Dn ) − Φ(D0 ) .

(3)

i=1

összefüggés adja. Ha olyan Φ potenciálfüggvényt tudunk adni, hogy Φ(Dn ) ≥ Φ(D0 ) teljesüljön, akkor a ∑ni=1 cbi amortizációs költség felso˝ korlátja lesz a ∑ni=1 ci tényleges költségnek. Verem muvelek ˝ Definiáljuk a Φ potenciálfüggvényt a veremben lévo˝ elemek számaként. Kezdetben Φ(D0 ) = 0. Mindig teljesül a

Φ(Di )

0 = Φ(D0 )

≥

˝ egyenlotlenség. A V EREMBE muvelet ˝ végrehajtásakor a potenciál változás:

Φ(Di ) − Φ(Di−1 )

=

2

(|V | + 1) − |V | = 1 .

Tehát a V EREMBE muvelet ˝ amortizációs költsége:

cbi

=

ci + Φ(Di ) − Φ(Di−1 )

=

1+1 = 2

A K IVESZ (V, K ) muveletre ˝

Φ(Di ) − Φ(Di−1 ) = −k0 . ahol k0 = min(|V |, k). Tehát az amortizációs költség:

cbi

=

ci + Φ(Di ) − Φ(Di−1 )

=

k0 − k0 = 0 .

Ehhez hasonlóan, a V EREM B OL muvelet ˝ amortizációs költsége is 0. Tehát mindhárom muvelet ˝ amortizációs költsége O(1), ezért a teljes muveletsor ˝ amortizációs költsége O(n). Mivel már láttuk, hogy Φ(Di ) ≥ Φ(D0 ), így n muvelet ˝ teljes amortizációs költsége felso˝ korlátja a tényleges költségnek, tehát a tényleges összköltség legrosszabb esetben O(n). Bináris számláló Definiáljuk a potenciálfüggvényt az i-edik N OVEL muvelet ˝ után a bi értékként, ami a számláló 1-einek száma az i-edik muvelet ˝ után. ˝ 0-ra. Ezért a tényleges költség Számítsuk ki a N OVEL muvelet ˝ amortizációs költségét. Tegyük fel, hogy az i-edik muvelet ˝ ti bitet változtat 1-rol legfeljebb ti + 1, ami ti bit 1-re állítását és legfeljebb egy bitnek 0-rol 1-re változtatásából áll. Ha bi = 0, akkor a muvelet ˝ mind a k bitet 0-ra állítja, ezért bi−1 = ti = k. Ha bi > 0, akkor bi = bi−1 − ti + 1. Mindkét esetben bi ≤ bi−1 − ti + 1, és a potenciálváltozás

Φ(Di ) − Φ(Di−1 )

≤

(bi−1 − ti + 1) − bi−1

=

1 − ti .

Az amortizált költség tehát

cbi

=

ci + Φ(Di ) − Φ(Di−1 )

≤

(ti + 1) + (1 − ti ) = 2 .

Ha a számláló 0-rol indul, akkor Φ(D0 ) = 0. Mivel minden i-re Φ(Di ) ≥ 0, így n N OVEL muvelet ˝ sorozatának teljes amortizált költsége felso˝ korlátja lesz a tényleges költségnek, ami legrosszabb esetben O(n). A potenciál módszerrel elemezheto˝ az az eset is, amikor a számláló nem 0-ról indul. Kezdetben b0 1-es van benne, az i-edik N OVEL végrehajtása után pedig bn , ahol 0 ≤ b0 , bn ≤ k. A (2) egyenlet átrendezésével kapjuk, hogy n

n

i=1

i=1

∑ ci = ∑ cbi − Φ(Dn ) + Φ(D0 ) .

Tehát cbi ≤ 2 minden 1 ≤ i ≤ n esetén. Mivel Φ(D0 ) = b0 és Φ(Dn ) = bn , a tényleges költsége n N OVEL muveletnek ˝ n

∑ ci

n

≤

∑ 2 − bn + b0

=

2n − bn + b0 .

i=1

10.4.

i=1

Dinamikus táblák

Type Elemtip=???; Tabla=Record meret:Longint; eszam:Longint; Tar:^Array[1..MaxLongint] of Elemtip; End; 10.4.1.

Tábla kiterjesztése

Procedure Beszur(Var T:Tabla; x:Elemtip); Var UT:Tabla; i:Longint; Begin If T.meret=0 Then Begin GetMem(T.Tar,Sizeof(Elemtip)); T.meret:=1; T.eszam:=0; 3

(4)

End; If T.szam=T.meret Then Begin UT.meret:=2*T.meret; Getmem(UT.Tar, UT.meret*Sizeof(Elemtip)); UT.eszam:=T.eszam; For i:=1 To T.eszam Do UT.Tar^[i]:=T.Tar^[i]; MreeMem(T.Tar,T.meret*Sizeof(Elemtip)) T:=UT; End; Inc(T.eszam); T.Tar^[T.eszam]:=x; End;  ci =

i 1

if i − 1 2-hatvány , különben .

n B ESZUR teljes költsége blg nc

n

∑ ci

≤

n+

i=1

∑

2j

j=0

<

n + 2n

=

3n ,

Potenciál módszer

Φ(T ) = 2T. eszam −T. meret

(5)

˝ Minden kiterjesztés után közvetlenül T.eszam = T.meret/2 + 1, vagyis Φ(T ) = 2, közvetlenül elotte pedig T.eszam = T.meret , így Φ(T ) = T.eszam. Φ(T ) mindig nemnegatív. Legyen az i-edik muvelet ˝ után közvetlenül szami a tárolt elemek száma, mereti a tábla mérete és Φi a potenciálfüggvény értéke. Kezdetben szam0 = meret0 = Φ0 = 0. Ha az i-edik B ESZUR muvelet ˝ nem váltja ki a tábla kiterjesztését, akkor mereti = mereti−1 , így az amortizációs költsége:

cbi

=

ci + Φi − Φi−1

=

1 + (2 · eszami − mereti ) − (2 · eszami−1 − mereti−1 )

=

1 + (2 · eszami − mereti ) − (2(eszami −1) − mereti )

=

3.

˝ következik, Ha az i-edik B ESZUR muvelet ˝ kiváltja a tábla kiterjesztését, akkor mereti = 2 · mereti−1 és mereti−1 = eszami−1 = eszami −1, amibol hogy mereti = 2 · (eszami −1). Tehát az amortizációs költség:

cbi

10.4.2.

=

ci + Φi − Φi−1

=

eszami +(2 · eszami − mereti ) − (2 · eszami−1 − mereti−1 )

=

eszami +(2 · eszami −2 · (eszami −1)) − (2(eszami −1) − (eszami −1))

=

eszami +2 − (eszami −1)

=

3

Tábla kiterjesztése és összehúzása

˝ Jelölje α(T ) = T.eszam/T.meret értéket, tehát a tábla telítettségi tényezojét, αi az i-edik muvelt ˝ után a telítettség értéke. ˝ akkor csökkentsük felére a méretét. Az összehúzás stratégiája: ha a tábla félig van tele TOTOL muvelet ˝ elott, n B ESZUR, TOTOL muveletet ˝ tartalmazó muveletsor ˝ futási idejét vizsgáljuk. Definiáljuk a potenciálfüggvényt a következo˝ formulával:

Φi =



2 · eszami − mereti mereti /2 − eszami

ha αi ≥ 1/2 , ha αi < 1/2 ,

˝ Eloször nézzük azt az esetet, amikor az i-edik muvelet ˝ B ESZUR. Ha αi−1 ≥ 1/2, akkor az elemzés azonos a korábbi esettel, amikor csak B ESZUR muveletet ˝ végeztünk, tehát cbi legfeljebb 3. Ha αi−1 < 1/2, akkor nem lép fel kiterjesztés, mert azt csak αi−1 = 1 esetben kell végezni. Ha még

4

αi < 1/2 is teljesül, akkor cbi

=

ci + Φi − Φi−1

=

1 + (mereti /2 − numi ) − (mereti−1 /2 − numi−1 )

=

1 + (mereti /2 − numi ) − (mereti /2 − (numi −1))

=

0.

Ha αi−1 < 1/2 de αi ≥ 1/2, akkor

ci + Φi − Φi−1

=

cbi

=

1 + (2 · numi − mereti ) − (mereti−1 /2 − numi−1 )

=

1 + (2(numi−1 +1) − mereti−1 ) − (mereti−1 /2 − numi−1 ) 3 3 · numi−1 − mereti−1 +3 2 3 3αi−1 mereti−1 − mereti−1 +3 2 3 3 mereti−1 − mereti−1 +3 2 2 3

= = < =

Tehát akár van, akár nincs kiterjesztés, a cbi amortizált költség legfeljebb 3. Tekintsük most azt az esetet, amikor az i-edik muvelet ˝ TOROL. Ekkor eszami = eszami−1 −1. Ha αi−1 < 1/2, akkor figyelembe kell venni, hogy sor kerül összehúzásra. Ha nem, akkor mereti = mereti−1 és így az amortizált költség

cbi

=

ci + Φi − Φi−1

=

1 + (mereti /2 − eszami ) − (mereti−1 /2 − eszami−1 )

=

1 + (mereti /2 − eszami ) − (mereti /2 − (eszami +1))

=

2

Ha αi−1 < 1/2 és a TOROL muvelet ˝ összehúzást vált ki, akkor ci = eszami +1, mivel egy elemet törlünk és eszami számú elemet átmozgatunk. Kapjuk, hogy mereti /2 = mereti−1 /4 = eszami−1 = eszami +1, így az amortizált költség

cbi

=

ci + Φi − Φi−1

=

(eszami +1) + (mereti /2 − eszami ) − (mereti−1 /2 − eszami−1 )

=

(eszami +1) + ((eszami +1) − eszami ) − ((2 · eszami +2) − (eszami +1))

=

1.

Ha az i-edik muvelet ˝ TOROL és αi−1 ≥ 1/2, akkor is konstans felso˝ korlát van az amortizált költségre.

5