Algorytmy i Struktury Danych

7. Analiza kosztu zamortyzowanego

1. (1p.) Czy ograniczenie O(1) na koszt zamortyzowany operacji na stosie

pozostanie w mocy, jeśli dopuścimy operację Multipush, która umożliwia
jednoczesne umieszczanie wielu elementów na stosie?

2. (1p.) Uzasadnij, ze jeśli dopuścimy operację Decrement, która zmniejsza

wartość k-bitowego licznika o 1, to ciąg n operacji może wymagać czasu
Θ(nk).

3. (1p.) Wykonujemy ciąg n operacji na strukturze danych. Koszt i-tej ope-

racji jest równy i jeśli i jest potęgą dwójki; w przeciwnym razie wynosi
1. Dokonaj analizy kosztu zamortyzowanego metodami kosztu sumarycz-
nego, księgowania i potencjału.

4. (2p.) Załóżmy, że oprócz operacji zwiększania możemy także zerować

licznik (tzn. zerować wszystkie bity) za pomocą operacji Reset. Pokaż jak
zaimplementować licznik, aby czas działania dowolnego ciągu n operacji
Increment

i Reset, działających na początkowo wyzerowanym liczniku,

wynosił O(n). (Wskazówka: Zapamiętuj wskaźnik do następnej jedynki.)

5. (1p.) Niech dana będzie funkcja potencjału Φ taka, że Φ(D

i

) ≥ Φ(D

0

)

dla każdego i, lecz Φ(D

0

) 6= 0. Wykaż, że istnieje funkcja potencjału

Φ

′

spełniająca warunki Φ

′

(D

0

) = 0, Φ

′

(D

i

) ≥ 0 dla i ≥ 1 oraz koszty

zamortyzowane operacji względem Φ

′

są takie same jak względem Φ.

6. (2p.) Rozważ zwyczajny binarny n-elementowy kopiec, na którym są do-

puszczalne operacje Insert i Extract-Min, których pesymistyczny koszt
działania wynnosi O(lg n). Podaj funkcję potencjału Φ, względem której
koszt zamortyzowany operacji Insert wynosi O(lg n), a koszt zamortyzo-
wany Extract-Min wynosi O(1).

7. (1p.) Jaki jest koszt wykonania na stosie n operacji Push, Pop, Multipop

przy założeniu, że na początku wyokość stosu wynosi s

0

, a po n operacjach

s

n

.

8. (1p.) Zakładając, że licznik zaczyna zliczać nie od zera, lecz od pewnej

liczby z b jedynkami w jej binarnej reprezentacji, wykaż, że koszt wykona-
nia n operacji Increment jest O(n), jeśli n = Ω(b).

9. (2p.) Pokaż jak zaimplementować kolejkę za pomocą dwóch zwyczajnych

stosów, aby koszt zamortyzowany każdej operacji Insert i Delete wynosił
O(1).

10. (1p.) Wyjaśnij intuicyjnie, dlaczego jeśli α

i−1

≤ 1/2 oraz α

i

≤ 1/2, to

koszt zamortyzowany operacji Table-Insert jest równy 0.

1

11. (2p.) Chcemy zaimplementować tablicę z haszowaniem z wykorzystaniem

adresowania otwartego. Dlaczego lepiej traktować ją jako zapełnioną już
gdy współczynnik zapełnienia przekracza pewną stałą mniejszą niż 1? Jak
zagwarantować, że oczekiwany czas zamortyzowany operacji wstawiania
do takiej tablicy jest O(1)? Dlaczego oczekiwany faktyczny czas wstawia-
nia nie musi być dla wszystkich operacji O(1)?

12. (1p.) Wykaż, że jeśli i-tą operacją na tablicy dynamicznej jest Table-Delete

oraz α

i−1

≥ 1/2, to koszt zamortyzowany tej operacji względem podanego

na wykładzie potencjału jest ograniczony przez stałą.

13. (1p.) Przyjmij, że zamiast dwukrotnego zmniejszania rozmiaru tablicy,

gdy wspólczynnik zapełnienia spada poniżej 1/4, zmnejszamy jej rozmiar
mnożąc go przez 2/3 gdy współczynnik zapełnienia spada poniżej 1/3.
Użyj funkcji potencjału: Φ(T ) = |2 · num[T ] − size[T ]| by wykazać, że
koszt zamortyzowany operacji Table-Delete jest stały.

2