Alg10 - Lecture notes 10 PDF

Preview

Summary

All you need to know from lecture....

Description

Katedra Aparatów Elektrycznych Alg10 Dr J. Dokimuk

Algorytmy i Struktury Danych – wykład/1st

2014-03-02

171

Katedra Aparatów Elektrycznych Alg10 Dr J. Dokimuk

Algorytmy i Struktury Danych – wykład/1st

172

2014-03-02

10.1. Metoda kosztu sumarycznego

10. KOSZT ZAMORTYZOWANY Czas wykonania ciągu operacji na danych jest dzielony równo między operacje.

Analiza ciągu n operacji stosowych: Pop, Push i MultiPOP (w chwili startu stos jest pusty).

 Analiza kosztu zamortyzowanego nie korzysta z metod probabilistycznych.

Pozwala wykazać, że średni koszt przetworzenia danych może być mały, mimo że pojedyncze operacje są bardzo kosztowne.

Czas działania operacji MultiPOP(k,S) jest proporcjonalny do liczby wykonanych operacji Pop, gdyż liczba obiegów pętli while jest równa liczbie k obiektów zdjętych ze stosu.

while ( not Empty(S) and k ≠ 0 ) Pop(S)

Metody analizy kosztu zamortyzowanego:  metoda kosztu sumarycznego: określa górne ograniczenia T(n) całkowitego kosztu ciągu n operacji. Kosztem zamortyzowanym każdej operacji jest T(n)/n .

Koszt zamortyzowany jest jednakowy dla każdej operacji, nawet gdy w ciągu występują operacje różnych typów.

Pesymistyczny czas działania pojedynczej operacji MultiPOP(k,S) określa O(n), gdy rozmiar stosu zawiera n elementów (zaś k = n).

Pesymistyczny koszt ciągu n operacji stosowych jest klasy O(n2): -w ciągu może być n operacji MultiPOP(),

for i = 1 to n do MultiPOP(…)

 metoda księgowania: wyznacza koszt zamortyzowany każdej operacji (różne typy operacji mogą mieć inne koszty zamortyzowane).

-każda z nich ma pesymistyczny koszt O(n).

 Koszt operacji na początku ciągu jest zawyżony, wiążąc „nadpłaty" z pewnymi Obiektami w strukturze danych.

Złożoność O(n2) wynika z rozpatrywania kosztu każdej operacji z osobna i można ją poprawić.

Powstały kredyt zostanie zużyty na „zapłacenie" za operacje, których faktycznie poniesione koszty są wyższe niż wkład.

 Każdy obiekt włożony na stos, może być z niego zdjęty co najwyżej jeden raz 

 metoda potencjału: przypisuje większy koszt wcześniejszym operacjom. Kredyt jest „energią potencjalną" całej struktury danych i nie jest związany z pojedynczymi obiektami. Kredyty przypisywane Obiektom danych służą wyłącznie do analizy i nie trzeba uwzględniać ich przy implementacji algorytmów. Analiza kosztu zamortyzowanego konkretnej struktury danych może pomóc w jej modyfikacji.

Stos z operacją

ze stosu S

lub

opróżnia go, jeśli na stosie było mniej niż k elementów. MultiPOP(k, S)

while ( not Empty(S) and k ≠ 0 ) Pop(S) k=k-1 -----------------------Standardowe operacje Pop(S) i Push(el, S) działają w czasie O(1)

Czas działania ciągu n tych operacji wynosi O(n)

for i = 1 to n do Pop(S)

for i = 1 to n do Push(i, Sn)

O(n)

for i = 1 to n do MultiPOP(n, Si )

Zastosowanie kosztu zamortyzowanego ilustruje stos z operacją MultiPOP(k, S)

elementów

nie może być większa niż liczba operacji Push, która nie jest większa niż n.

n = 10;

MultiPOP(k,S)

Operacja MultiPOP(k,S) usuwa k

Stąd liczba wywołań funkcji Pop - włączając w to wywołania wewnątrz operacji MultiPOP(k,S)

n … 4 3 2 1

n … 4 3 2 1

Dla dowolnego n łączny czas wykonania każdego ciągu n operacji Pop, Push i MultiPOP wynosi co najwyżej O(n). Wykazaliśmy, że O(n) jest pesymistycznym kosztem ciągu n operacji. Dzieląc całkowity koszt przez n, otrzymujemy średni koszt przypadający na operację, czyli koszt zamortyzowany równy O(n)/n = O(1).

Katedra Aparatów Elektrycznych Alg10 Dr J. Dokimuk

Algorytmy i Struktury Danych – wykład/1st

2014-03-02

173

10.2. Metoda księgowania

Katedra Aparatów Elektrycznych Alg10 Dr J. Dokimuk

Algorytmy i Struktury Danych – wykład/1st

Analizę rozpoczynamy od pustego stosu.

Metoda przypisuje różne koszty zamortyzowane różnym rodzajom operacji.

Kładąc Obiekt na stosie płacimy 1 zł za faktyczny koszt położenia.

Jedne z nich będą większe, inne mogą być mniejsze niż koszt faktyczny. Jeśli koszt zamortyzowany operacji jest większy niż jej koszt faktyczny, to różnica tych kosztów przypisywana jest pewnym Obiektom danych (księgowana) jako kredyt.

174

2014-03-02

Zostaje 1 zł (koszt zamortyzowany Push wynosi 2 zł), co kładziemy obok Obiektu.

1zł 1zł 1zł 1zł

W każdej chwili każdy Obiekt na stosie zawiera 1 zł kredytu.

Gotówka na stosie stanowi przedpłatę na koszt zdjęcia go ze stosu.

Kredytem można płacić za operacje, których faktyczny koszt jest większy niż ich koszt zamortyzowany.

Za wykonanie operacji Pop nie jest pobierana opłata, gdyż możemy zapłacić za nią kredytem dostępnym na stosie.

Koszt zamortyzowany operacji dzieli się na:

Zdejmując Obiekt ze stosu, zdejmujemy z niego kredyt, którym opłacamy koszt operacji.

-koszt faktyczny, -kredyt, który może być w depozycie, albo być wykorzystywany.

 Pobierając od operacji Push więcej niż wynosi jej faktyczny koszt, nie musimy pobierać opłaty od operacji Pop.

Koszty zamortyzowane poszczególnych operacji należy dobierać ostrożnie.

Aby wykazać, że w najgorszym przypadku średni koszt operacji jest mały, należy zapewnić, że całkowity koszt zamortyzowany ciągu operacji stanowi górne ograniczenie faktycznego kosztu tego ciągu.  Należy udowodnić tę własność dla wszystkich ciągów operacji. Suma kredytów związanych z Obiektami danych nie może być ujemna: gdyż określa ona, o ile całkowity koszt zamortyzowany ciągu operacji przekracza koszt faktyczny. Jeśli dopuścimy do ujemnego kredytu (zbyt mały kredyt od wcześniejszych operacji, zakładając że później poczyni się oszczędności), to całkowity koszt zamortyzowany naliczony do tej chwili będzie mniejszy niż koszt faktycznie wydatkowany. Dla ciągu operacji od początku do tej właśnie chwili, całkowity koszt zamortyzowany nie stanowi wtedy górnego ograniczenia kosztu faktycznego. Faktyczne koszty operacji na stosie są następujące: gdzie k jest liczbą elementów zdejmowanych ze stosu. Pop

1

Push MultiPOP(k, S)

1 k

Stosowym operacjom przypisano następujące koszty zamortyzowane: Pop

0

MultiPOP(k, S) Push

0 2

Koszt zamortyzowany operacji MultiPOP() przyjęto jako stały choć faktycznie jest zmienny (bo ).  Za każdy ciąg operacji na stosie można zapłacić za pomocą zaksięgowanego kosztu zamortyzowanego. Niech jednostką kosztu będzie 1 zł.

Nie musimy obciążać opłatami operacji MultiPOP. while ( not Empty(S) and k ≠ 0 ) Pop(S) 1zł 1zł 1zł 1zł

Aby zdjąć 1-szy Obiekt bierzemy z niego 1 zł kredytu i płacimy za operację

.

Aby zdjąć 2-gi Obiekt wystarczy zrobić to samo, itd. W każdej chwili wystarczą pobrane wcześniej opłaty za operacje Push na zapłacenie realizowanych teraz operacji MultiPOP.

Ponieważ na każdym Obiekcie znajduje się 1 zł kredytu, a na stosie jest zawsze nieujemna liczba Obiektów, kredyt jest zawsze wielkością nieujemna. Zatem dla ż ciągu n operacji Pop, Push i MultiPOP ich koszt zamortyzowany stanowi górne ograniczenie faktycznego kosztu wykonania tych operacji. Całkowity koszt zamortyzowany określony jest przez O(n), tym bardziej jest to słuszne dla kosztu faktycznego.

Katedra Aparatów Elektrycznych Alg10 Dr J. Dokimuk

Algorytmy i Struktury Danych – wykład/1st

2014-03-02

175

Katedra Aparatów Elektrycznych Alg10 Dr J. Dokimuk

Algorytmy i Struktury Danych – wykład/1st

2014-03-02

176

10.3.1. Operacje na stosie: Pop, Push i MultiPOP

10.3. Metoda potencjału W metodzie potencjału nadpłata kosztu stanowi „energię potencjalną", która może być użyta do opłacenia późniejszych operacji.

Definiujemy funkcję potencjału Φ na stosie jako jego wysokość.

Potencjał związany jest ze strukturą danych jako całością, a nie z jej pojedynczymi obiektami.

Dla stosu pustego Φ(D0 ) = 0. Wysokość stosu jest zawsze nieujemna, więc Φ(Di) > 0.

Dana jest struktura danych D0 , na której chcemy wykonać n operacji.

Całkowity koszt zamortyzowany ciągu n operacji ze względu na Φ stanowi górne ograniczenie faktycznego kosztu.

Niech ci oznacza faktyczny koszt i-tej operacji, dla każdego i = 1, 2, ..., n; Niech Di będzie strukturą danych powstałą ze struktury Di-1 po wykonaniu i-tej operacji. Funkcja potencjału Φ przyporządkowuje każdej strukturze Di liczbę rzeczywistą Φ(D i), zwaną potencjałem struktury D i.

 Koszt zamortyzowany operacji stosowych dla stosu m elementowego.  Operacja Push ( i-ta operacja na stosie): przyrost potencjału wynosi:

Φ(Di) - Φ(Di-1) = (m+1) – m = 1

Koszt zamortyzowany ĉ i dla i-tej operacji względem funkcji potencjału Φ definiuje zależność: Koszt zamortyzowany operacji

ĉi = c i +[ Φ(Di) - Φ(Di-1 ) ]

Faktyczny koszt tej operacji wynosi: r Przyrost potencjału wynosi: Φ(Di) - Φ(Di-1) = -r

Całkowity koszt zamortyzowany ciągu n operacji wynosi:

∑ 1

∑( 1

(

)

(

1 ))

∑

Koszt zamortyzowany (

)

ĉi = ci + Φ(Di) - Φ(Di-1 ) = 1 + 1 = 2

 Operacja MultiPOP(): wykonanie operacji zdejmuje ze stosu r elementów.

Koszt zamortyzowany każdej operacji jest sumą: -kosztu faktycznego. -przyrostu potencjału związanego z wykonaniem danej operacji.

ˆ

:

(10.1)

(

(10.2)

0)

∑( 1

1)

ĉi = ci + Φ(Di) - Φ(D i-1) = r – r = 0

 Operacja Pop: koszt zamortyzowany wynosi 0.

1

gdyż, dla dowolnego ci ągu a0, a1, ..a n:

():

Koszt zamortyzowany wszystkich trzech operacji wynosi O(1). 0

Całkowity koszt zamortyzowany całego ciągu n operacji jest równy O(n).

Jeśli Φ(Dn) ≥ Φ(D0 ) to

∑ˆ

jest ograniczeniem z góry całkowitego kosztu faktycznego.

1

W praktyce nie wiemy zazwyczaj, ile operacji zostanie wykonanych. Jeżeli Φ(D i) ≥ Φ(D0) dla każdego i, to mamy gwarancję, że płacimy zawsze z góry. Zwykle definiuje się Φ(D 0 ) = 0

 Należy wykazać, że Φ(Di) ≥ 0 dla każdego i Jeśli przyrost potencjału Φ(Di) - Φ(D i-1) > 0 przy i-tej operacji: -to koszt zamortyzowany ĉi daje nadpłatę przy i-tej operacji, -więc potencjał struktury danych wzrasta. Jeśli Φ(D i) - Φ(Di-1 ) < 0, to: -koszt zamortyzowany i-tej operacji jest mniejszy niż jej koszt rzeczywisty; -niedopłata powoduje spadek potencjału struktury danych.  Definiując różne funkcje potencjału Φ, można otrzymać różne koszty zamortyzowane i mimo wszystko otrzymać górne ograniczenia kosztu faktycznego.

Ponieważ Φ(D i) ≥ Φ(D 0), zatem całkowity koszt zamortyzowany n operacji na stosie stanowi górne ograniczenie ich faktycznego kosztu. Stąd pesymistyczny koszt ciągu n operacji wynosi O(n)....