Dynamické pole s přidáváním prvků na konec
Máme datovou strukturu dynamického pole s jedinou operací Insert, která přidává prvky na konec.
Dynamické pole si drží dva údaje – velikost (počet prvků, size) a kapacitu (rozměr alokované paměti,
capacity). Na počátku nemá pole alokovánu žádnou paměť – jeho velikost i kapacita je 0. Operace
Insert funguje následovně:
• Je-li kapacita rovna 0, alokuj paměť o kapacitě 1.
• Je-li aktuální velikost rovná kapacitě, alokuj novou paměť o dvojnásobné kapacitě, přesuň do ní
všechny prvky ze staré paměti a dealokuj starou paměť.
• Vlož prvek na konec pole a zvětši velikost pole o 1.
Pro velikost a kapacitu dynamického pole P budeme dále používat notaci size(P) a capacity(P).
Cena operace Insert je dána následovně (cena je dána pouze přesuny prvků, alokaci/dealokaci paměti
do složitosti pro zjednodušení nepočítáme):
• Pokud size(P) = capacity(P), pak Insert stojí size(P) + 1.
• Jinak Insert stojí 1.
Dokážeme nyní metodou potenciálové funkce, že amortizovaná složitost Insert je konstantní, tedy že
libovolná posloupnost operací Insert délky n má složitost v O(n).
Vhodná potenciálová funkce musí být dostatečně vysoká před provedením „drahého“ Insertu a
dostatečně nízká po něm. Zároveň nesmí nikdy klesnout pod svou počáteční hodnotu.
Zvolíme potenciálovou funkci Φ(P) = 2 · size(P) − capacity(P). Počáteční hodnota této potenciálové
funkce je 0; zároveň je jasné, že nikdy v průběhu vykonávání Insertů nebude hodnota potenciálové funkce
menší než 0, protože je implementací operace Insert zaručeno, že vždy platí size(P) ≥ capacity(P)/2.
Zbývá tedy spočítat amortizovanou cenu i. operace Insert, pro všechna i od 1 do n. Budeme používat
následující notaci: Pi značí stav dynamického pole po provedení i. operace. Počáteční stav pole je tedy
označen P0.
„Levný“ Insert: Platí size(Pi−1) < capacity(Pi−1) a skutečná cena Insertu je ci = 1. Po provedení
Insertu pak víme, že capacity(Pi) = capacity(Pi−1) a size(Pi) = size(Pi−1) + 1. Pak platí:
ˆci = ci + Φ(Pi) − Φ(Pi−1)
= 1 + (2 · size(Pi) − capacity(Pi)) − (2 · size(Pi−1) − capacity(Pi−1))
= 1 + (2 · (size(Pi−1) + 1) − capacity(Pi−1)) − (2 · size(Pi−1) − capacity(Pi−1))
= 1 + 2 = 3
„Drahý“ Insert: Platí size(Pi−1) = capacity(Pi−1) a skutečná cena Insertu je ci = size(Pi−1) + 1.
Po provedení Insertu pak víme, že capacity(Pi) ≥ 2 · capacity(Pi−1)1
a size(Pi) = size(Pi−1) + 1. Pak
platí:
ˆci = ci + Φ(Pi) − Φ(Pi−1)
= (size(Pi−1) + 1) + (2 · size(Pi) − capacity(Pi)) − (2 · size(Pi−1) − capacity(Pi−1))
≤ (size(Pi−1) + 1) + (2 · (size(Pi−1) + 1) − 2 · capacity(Pi−1)) − (2 · size(Pi−1) − capacity(Pi−1))
= size(Pi−1) + 1 + 2 − capacity(Pi−1) = 3
Ve všech případech je tedy ˆci shora omezeno konstantou 3, a proto
n
i=1 ci ≤
n
i=1 ˆci ≤ 3 · n ∈ O(n).
Dynamické pole s odebíráním prvků z konce
Nejjednodušší varianta bez zmenšování
Nejjednodušší možnost je při mazání pole nijak nezmenšovat. Operace Delete je pak vždy zaručeně
konstantní, přičemž složitost operace Insert se nijak nezhorší. Striktně vzato bychom ale při analýze
1To zahrnuje jak případ s capacity(Pi−1) = 0, kdy capacity(Pi) = 1, tak případ s capacity(Pi−1) > 0, kdy
capacity(Pi) = 2 · capacity(Pi−1). Všimněte si, že z tohoto důvodu se v následujícím výpočtu objeví ≤.
1
amortizované složitost nemohli použít dříve uvedenou potenciálovou funkci (protože už nebude nutně
platit size(P) ≥ capacity(P)/2). Vhodná potenciálová funkce je v tomto případě tato:
Φ(P) =
2 · size(P) − capacity(P) pokud je size(P) ≥ capacity(P)/2
0 jinak
Výpočet ˆci ve všech případech (je třeba uvažovat obě operace!) necháváme čtenáři jako cvičení.
Špatná varianta se zmenšováním
Uvažujme nyní následující možnost: Delete smaže poslední prvek a pokud tím zaplnění dynamického
pole kleslo pod polovinu, alokuje se nová paměť polovičního rozměru a prvky se do ní přesunou.
Ukážeme, že tato varianta nemá dobrou amortizovanou složitost; konkrétně ukážeme, že existuje
posloupnost n operací Insert a Delete taková, jejíž celková složitost je v Ω(n2
). Skutečná cena Delete
je při zmenšování pole rovna size(P).
Nechť k je nejbližší mocnina dvou menší než nebo rovna n/2, tj. k = 2i
pro nějaké přirozené i takové,
že 2i
≤ n/2 < 2i+1
= 2 · k. Posloupnost operací sestavíme následovně:
• Nejprve kkrát provedeme operaci Insert.
• Následně (n − k)/4 krát provedeme čtveřici Insert, Delete, Delete, Insert.
• Pokud ještě nemáme posloupnost délky n, doplníme ji do délky n operacemi Insert (tyto operace
budou maximálně 3).
Je zřejmé, že po k provedeních operace Insert bude dynamické pole mít velikost i kapacitu rovnu k.
Cenu těchto operací ignorujeme (snažíme se nyní určit dolní odhad složitosti, takže si to můžeme
dovolit).
Cena každé čtveřice v druhé části posloupnosti je následující: k + 1 za první Insert, 1 za první Delete,
k za druhý Delete (přesun všech prvků), 1 za druhý Insert. Dohromady alespoň Ω(k). Takovýchto
čtveřic je v naší posloupnosti (n − k)/4 . Dolní odhad pro tento počet je:
(n − k)/4 ≥ (n − k)/4 ≥ (n − (n/2))/4 = n/8.
Celková cena posloupnosti je tedy alespoň k · (n/8). Protože n/2 < 2 · k, platí n/4 < k a cena
posloupnosti je tedy alespoň (n/4) · (n/8), což patří do Ω(n2
).
Poznámka: Všimněte si, že i v tomto případě je operace Insert amortizovaně konstantní, pokud
bychom ji uvažovali odděleně. Stejně tak operace Delete je amortizovaně konstantní, pokud bychom
ji uvažovali odděleně (např. tak, že začínáme s dostatečně velkým polem, na němž voláme pouze
posloupnost operací Delete). Je zde tedy vidět, že máme-li víc operací, není možné určovat jejich
amortizovanou složitost „po částech“, ale je třeba je uvažovat všechny zároveň.
Správná varianta se zmenšováním
Uvažujme nyní následující variantu: Delete smaže poslední prvek a pokud tím zaplnění dynamického
pole klesne přesně na čtvrtinu, alokujeme novou paměť polovičního rozměru a přesuneme prvky do
nové paměti. Pole o kapacitě menší než 4 (tj. 1 nebo 2) nebudeme zmenšovat vůbec. Cena operace
Delete je size(P), pokud capacity(P) ≥ 4 a size(P) = capacity(P)/4 + 1, jinak je 1.
Dokážeme nyní metodou potenciálové funkce, že amortizovaná složitost obou operací Insert i Delete je
konstantní, tedy že libovolná posloupnost operací Insert a Delete délky n má složitost v O(n).
Vhodná potenciálová funkce musí být dostatečně vysoká před provedením jakékoli „drahé“ operace
(tj. když je pole plné nebo když se jeho zaplnění blíží čtvrtině) a dostatečně nízká po provedení této
operace (tj. když je pole zaplněné do poloviny).
Potenciálová funkce uvedená v první části tohoto dokumentu splňuje jen část těchto požadavků. Zkusíme
to vyřešit tím, že ji zavřeme do absolutní hodnoty. Definujme tedy Φ(P) = |2 · size(P) − capacity(P)|.
Počáteční hodnota této funkce je 0; že nikdy neklesne pod 0 je dáno vlastností absolutní hodnoty.
Zbývá spočítat amortizovanou cenu i. operace (což může být Insert nebo Delete), pro všechna i
od 1 do n. Používáme stejnou notaci jako v prvním příkladu. Je třeba uvážit všechny možnosti.
2
Nezapomínejte, že ukazujeme horní odhad složitosti a stačí nám tedy, když bude amortizovaná cena
ˆci shora ohraničená námi požadovanou funkcí (v tomto případě konstantou).
„Levný“ Insert: Platí size(Pi−1) < capacity(Pi−1) a skutečná cena Insertu je ci = 1. Po provedení
Insertu víme, že capacity(Pi) = capacity(Pi−1) a size(Pi) = size(Pi−1) + 1. Pak platí:
ˆci = ci + Φ(Pi) − Φ(Pi−1)
= 1 + |2 · size(Pi) − capacity(Pi)| − |2 · size(Pi−1) − capacity(Pi−1)|
= 1 + |2 · (size(Pi−1) + 1) − capacity(Pi−1)| − |2 · size(Pi−1) − capacity(Pi−1)|
= 1 + |2 · size(Pi−1) − capacity(Pi−1) + 2| − |2 · size(Pi−1) − capacity(Pi−1)|
V tuto chvíli je třeba další výpočet rozvětvit podle toho, jak se realizují absolutní hodnoty v našem
výrazu. První možnost: size(Pi−1) ≥ capacity(Pi−1)/2. V tom případě pak jsou výrazy uvnitř obou
absolutních hodnot nezáporné a můžeme pokračovat takto:
ˆci = 1 + (2 · size(Pi−1) − capacity(Pi−1) + 2) − (2 · size(Pi−1) − capacity(Pi−1))
= 1 + 2 = 3
Druhá možnost: size(Pi−1) < capacity(Pi−1)/2. V tom případe jsou výrazy uvnitř obou absolutních
hodnot nekladné (zde je důležité si uvědomit, že size(Pi−1) je celé číslo) a můžeme pokračovat takto
(všimněte si výměny znamének):
ˆci = 1 − (2 · size(Pi−1) − capacity(Pi−1) + 2) + (2 · size(Pi−1) − capacity(Pi−1))
= 1 − 2 = −1
Vadí nám nějak, že nám vyšlo záporné číslo? Nevadí, stále je to konstanta.
„Drahý“ Insert: Platí size(Pi−1) = capacity(Pi−1) a skutečná cena Insertu je ci = size(Pi−1) + 1.
Po provedení Insertu pak víme, že capacity(Pi) ≥ 2 · capacity(Pi−1) (viz poznámku v prvním příkladu)
a size(Pi) = size(Pi−1) + 1. Pak platí:
ˆci = ci + Φ(Pi) − Φ(Pi−1)
= (size(Pi−1) + 1) + |2 · size(Pi) − capacity(Pi)| − |2 · size(Pi−1) − capacity(Pi−1)|
= (size(Pi−1) + 1) + (2 · size(Pi) − capacity(Pi)) − (2 · size(Pi−1) − capacity(Pi−1))
≤ (size(Pi−1) + 1) + (2 · (size(Pi−1) + 1) − 2 · capacity(Pi−1)) − (2 · size(Pi−1) − capacity(Pi−1))
= size(Pi−1) + 1 + 2 − capacity(Pi−1) = 3
Krok od druhého k třetímu řádku si můžeme dovolit, protože víme, že size(Pi−1) ≥ capacity(Pi−1)/2
a totéž platí pro Pi.
„Levný“ Delete: Platí buď capacity(Pi−1) < 4 nebo size(Pi−1) > capacity(Pi−1)/4. Skutečná
cena Delete je 1. Po provedení Delete pak víme, že capacity(Pi) = capacity(Pi−1) a size(Pi) =
max(size(Pi−1) − 1, 0) (z prázdného pole zřejmě není možno nic odebrat). Nejdříve vyřešíme situaci
capacity(Pi−1) < 4:
ˆci = ci + Φ(Pi) − Φ(Pi−1)
= 1 + |2 · size(Pi) − capacity(Pi)| − |2 · size(Pi−1) − capacity(Pi−1)|
Zřejmě první absolutní hodnota nemůže být větší než 3 (dá se snadno ověřit vyzkoušením všech
možných hodnot size(Pi) ≤ capacity(Pi) < 4). Zároveň druhá absolutní hodnota nemůže být menší
než 0 (to je vlastnost absolutní hodnoty). Proto můžeme náš výraz omezit takto:
ˆci ≤ 1 + 3 − 0 = 4
(Jistě, přesnější výpočet by nám tento výraz omezil více, ale proč? Počítáme asymptotickou složitost,
tedy nám nezáleží na velikosti konstanty.)
Dále vyřešíme situaci capacity(Pi−1) ≥ 4. Nyní jistě víme, že size(Pi−1) = size(Pi−1) − 1.
ˆci = ci + Φ(Pi) − Φ(Pi−1)
= 1 + |2 · size(Pi) − capacity(Pi)| − |2 · size(Pi−1) − capacity(Pi−1)|
= 1 + |2 · (size(Pi−1) − 1) − capacity(Pi−1)| − |2 · size(Pi−1) − capacity(Pi−1)|
= 1 + |2 · size(Pi−1) − capacity(Pi−1) − 2| − |2 · size(Pi−1) − capacity(Pi−1)|
3
Podobně jako výše u „levného“ Insertu, musíme nyní výpočet rozvětvit podle toho, jak se realizují
absolutní hodnoty. První možnost: size(Pi−1) > capacity(Pi−1)/2. V tom případě jsou výrazy uvnitř
obou absolutních hodnot nezáporné:
ˆci = 1 + (2 · size(Pi−1) − capacity(Pi−1) − 2) − (2 · size(Pi−1) − capacity(Pi−1))
= 1 − 2 = −1
Druhá možnost: size(Pi−1) ≤ capacity(Pi−1)/2. V tom případě jsou výrazy uvnitř obou absolutních
hodnot nekladné:
ˆci = 1 − (2 · size(Pi−1) − capacity(Pi−1) − 2) + (2 · size(Pi−1) − capacity(Pi−1))
= 1 + 2 = 3
„Drahý“ Delete: Platí capacity(Pi−1) ≥ 4, size(Pi−1) = capacity(Pi−1)/4+1 a skutečná cena Delete
je size(Pi−1). Víme, že po provedení Delete platí size(Pi) = size(Pi−1) − 1 = capacity(Pi−1)/4 a
capacity(Pi) = capacity(Pi−1)/2.
ˆci = ci + Φ(Pi) − Φ(Pi−1)
= size(Pi−1) + |2 · size(Pi) − capacity(Pi)| − |2 · size(Pi−1) − capacity(Pi−1)|
= size(Pi−1) + |2 · capacity(Pi−1)/4 − capacity(Pi−1)/2| − |2 · size(Pi−1) − capacity(Pi−1)|
= size(Pi−1) + 0 − |2 · size(Pi−1) − capacity(Pi−1)|
= (capacity(Pi−1)/4 + 1) − |2 · (capacity(Pi−1)/4 + 1) − capacity(Pi−1)|
= capacity(Pi−1)/4 + 1 − |2 − capacity(Pi−1)/2|
Výraz uvnitř zbývající absolutní hodnoty je nekladný (víme, že capacity(Pi−1) ≥ 4) a proto pokračujeme
takto:
ˆci = capacity(Pi−1)/4 + 1 + (2 − capacity(Pi−1)/2)
= 3 − capacity(Pi−1)/4 ≤ 3
Všimněte si, že nám nijak nevadí, že nám vyšel výraz, který je závislý na kapacitě dynamického pole.
Podstatné je, že tento výraz umíme shora omezit konstantou, v tomto případě 3.
Ve všech případech je tedy ˆci shora omezeno konstantou 4, a proto
n
i=1 ci ≤
n
i=1 ˆci ≤ 4 · n ∈ O(n).
(Ano, pokud bychom byli přesnější, mohlo nám vyjít 3 · n, ale zajímá nás asymptotická složitost.)
4