Příklad - Amortizovaná složitost
Dynamické pole
Chceme dynamickou datovou strukturu, která zachovává dobré vlastnosti pole.
► Insert (vkládání na konec): Pokud je pole plné, zvětšíme jej na dvojnásobek. Dokážeme, že Insert je amortizovaně 0(1).
Příklad - Amortizovaná složitost
Dynamické pole
Chceme dynamickou datovou strukturu, která zachovává dobré vlastnosti pole.
► Insert (vkládání na konec): Pokud je pole plné, zvětšíme jej na dvojnásobek. Dokážeme, že Insert je amortizovaně 0(1).
► Delete (odebírání z konce): Jak?
Příklad - Amortizovaná složitost
Dynamické pole
Chceme dynamickou datovou strukturu, která zachovává dobré vlastnosti pole.
► Insert (vkládání na konec): Pokud je pole plné, zvětšíme jej na dvojnásobek. Dokážeme, že Insert je amortizovaně 0(1).
► Delete (odebírání z konce): Jak?
► Varianta 1: Nezmenšovat pole.
► Varianta 2: Když zaplnění klesne na polovinu, zmenšit pole na polovinu.
Příklad - Amortizovaná složitost
Dynamické pole
Chceme dynamickou datovou strukturu, která zachovává dobré vlastnosti pole.
► Insert (vkládání na konec): Pokud je pole plné, zvětšíme jej na dvojnásobek. Dokážeme, že Insert je amortizovaně 0(1).
► Delete (odebírání z konce): Jak?
► Varianta 1: Nezmenšovat pole.
► Varianta 2: Když zaplnění klesne na polovinu, zmenšit pole na polovinu.
► Varianta 3: Zmenšovat pole, až když klesne na čtvrtinu / třetinu.
Příklad - Amortizovaná složitost
Dynamické pole - další otázky k zamyšlení
► zásobník (přidávání/ubírání prvků na jednom konci)
► fronta?
► přidávání/ubírání prvků na obou koncích?
► vkládání dovnitř pole?
Příklad - Amortizovaná složitost
Dynamické pole - další otázky k zamyšlení
► zásobník (přidávání/ubírání prvků na jednom konci)
► fronta?
► přidávání/ubírání prvků na obou koncích?
► vkládání dovnitř pole?
► Můžu mít zaručenu složitost 0(1) i v nejhorším případě?
Příklad - Amortizovaná složitost
Dynamické binární vyhledávání
► binární vyhledávání v seřazeném poli
► přidávání do pole
Příklad - Amortizovaná složitost
Dynamické binární vyhledávání
► binární vyhledávání v seřazeném poli
► přidávání do pole
► nápad: udržovat seznam exponenciálně rostoucích polí
► jaká je (amortizovaná) složitost vkládání a vyhledávání?
Příklad - Amortizovaná složitost
Dynamické binární vyhledávání
► binární vyhledávání v seřazeném poli
► přidávání do pole
► nápad: udržovat seznam exponenciálně rostoucích polí
► jaká je (amortizovaná) složitost vkládání a vyhledávání?
Poznámka: obecná metoda (Bentley & Saxe, 1979)