Amortizovaná složitost - Příklad 1
Každý třetí
Mějme datovou strukturu zřetězený seznam s operacemi:
► Add(x) - přidá prvek na konec seznamu
► RemoveEachThird - projde celý seznam a odstraní každý třetí prvek seznamu
Skutečná cena operací:
► Add: 1
► RemoveEachThird: n, kde n je aktuální délka seznamu Dokažte, že amortizovaná složitost obou operací je konstantní.
Amortizovaná složitost - Príklad 2
Seřazený zásobník
Mějme zásobník, který podporuje následující operace:
► OrderedPush(x) - smaže z vrcholu zásobníku všechny prvky menší než x a pak na vrchol vloží x
► Pop(x) - odstraní prvek z vrcholu zásobníku (a vrátí jej)
Tento zásobník implementujeme pomocí jednostranně zřetězeného seznamu. Dokažte, že amortizovaná časová složitost obou operací je konstantní.
Amortizovaná složitost - Příklad 3
Binární počitadlo implementované jako „neomezené" pole bitů (na počátku 0).
► Mějme jednu operaci Increment. Dokažte, že je její amortizovaná cena konstantní.
Amortizovaná složitost - Příklad 3
Binární počitadlo implementované jako „neomezené" pole bitů (na počátku 0).
► Mějme jednu operaci Increment. Dokažte, že je její amortizovaná cena konstantní.
► Přidejme navíc operaci Reset, která počitadlo vynuluje. Rozmyslete, jak tuto operaci implementovat a dokažte, že amortizovaná složitost obou operací je stále konstantní.
Amortizovaná složitost - Příklad 3
Binární počitadlo implementované jako „neomezené" pole bitů (na počátku 0).
► Mějme jednu operaci Increment. Dokažte, že je její amortizovaná cena konstantní.
► Přidejme navíc operaci Reset, která počitadlo vynuluje. Rozmyslete, jak tuto operaci implementovat a dokažte, že amortizovaná složitost obou operací je stále konstantní.
► Co kdybychom chtěli mít i operaci Decrement?