13. Třídící algoritmy a násobení matic Minulou přednášku jsme probírali QuickSort, jeden z historicky prvních třídících algoritmů, které překonaly kvadratickou složitost aspoň v průměrném případě. Proč se dodnes používá, když známe algoritmy, které mají složitost Θ(n log n) i v nejhorším případě? Protože QuickSort se k paměti chová téměř sekvenčně, takže na dnešních počítačích běží rychle. Podívejme se na pár nápadů pro skutečné naprogramování tohoto algoritmu. Určitě nám vadí překopírovávat z a do pomocných polí. Naštěstí můžeme přerovnávat přímo v původním poli. Zleva budeme dávat prvky menší než pivot, zprava větší než pivot. Na toto stačí udržovat si dva indexy a a b, které značí, jak daleko vlevo (vpravo) už jsou správné prvky. Rekurzivní programy mají zbytečně velkou režii. Proto implementujme vlastní zásobník na hranice úseků, které zbývá setřídit. Vždy větší interval vložíme na zásobník a menší rovnou zpracujeme. Na zásobníku proto bude maximálně log n položek. Malé podproblémy dotřídíme nějakým triviálním algoritmem například InsertSortem. Odhadem pro n = 10 je to pro dnešní počítače výhodné (zjišťuje se experimentálně). Zoo třídících algoritmů Porovnejme nyní známé třídící algoritmy. Definice: Stabilní třídění říkáme takovému, které u prvků se stejnou hodnotou klíče zachová jejich vzájemné pořadí, v jakém byly na vstupu. (To se hodí například při lexikografickém třídění, kde se napřed třídí podle nejméně významné složky a pak podle významějších.) Definice: Pokud třídíme prvky na místě (tedy vstup dostaneme zadaný v poli a v tomtéž poli pak vracíme výstup), za pomocnou paměť třídícího algoritmu prohlásíme veškerou využitou paměť mimo vstupní pole. InsertSort MergeSort HeapSort QuickSort
Čas Θ(n2 ) Θ(n log n) Θ(n log n) Θ(n log n)
Pomocná paměť Θ(1) Θ(n) Θ(1) Θ(log n)
Poznámky k tabulce:
Stabilní + + − −
• QuickSort má jen průměrnou časovou složitost Θ(n log n). Můžeme ale říct, že porovnáváme průměrné časové složitosti, protože u ostatních algoritmů vyjdou stejně jako jejich časové složitosti v nejhorším případě. • HeapSort – třídění pomocí haldy. Do haldy vložíme všechny prvky a pak je vybereme. Celkem Θ(n) operací s haldou, každá za Θ(log n). Navíc tuto haldu mohu stavět i rozebírat v poli, ve kterém dostanu vstup. 1
2011-07-31
• MergeSort jde implementovat s konstantní pomocnou pamětí za cenu konstantního zpomalení, ovšem konstanta je neprakticky velká. • MergeSort je stabilní, když dělím pole na poloviny. Není při třídění spojových seznamů s rozdělováním prvků na sudé a liché. • QuickSort se dá naprogramovat stabilně, ale potřebuje lineárně pomocné paměti. Žádný algoritmus v tabulce netřídil rychleji než Θ(n log n). To není náhoda – následující věta nám říká, že to nejde: Věta: Každý deterministický třídící algoritmus, který tříděné prvky pouze porovnává a kopíruje, má časovou složitost Ω(n log n). (O průměrné časové složitosti pravděpodobnostních třídících algoritmů se dá dokázat podobná věta.) Důkaz: Dokážeme, že každý porovnávací třídící algoritmus potřebuje v nejhorším případě provést Ω(n log n) porovnání, což dává přirozený dolní odhad časové složitosti. Přesněji řečeno, dokážeme, že pro každý algoritmus existuje vstup libovolné délky n, na němž algoritmus provede Ω(n log n) porovnání. Bez újmy na obecnosti se budeme zabývat pouze vstupy, které jsou permutacemi množiny {1, . . . , n}. (Stačí nám najít jeden „těžkýÿ vstup, pokud ho najdeme mezi permutacemi, úkol jsme splnili.) Mějme tedy deterministický algoritmus a nějaké pevné n. Sledujme, jak algoritmus porovnává – u každého porovnání zaznamenáme polohy porovnávaných prvků tak, jak byly na vstupu. Jelikož algoritmus je deterministický, porovná na začátku vždy tutéž dvojici prvků. Toto porovnání mohlo dopadnout třemi různými způsoby (větší, menší, rovno). Pro každý z nich je opět jednoznačně určeno, které prvky algoritmus porovná, a tak dále. Po provedení posledního porovnání algoritmus vydá jako výstup nějakou jednoznačně určenou permutaci vstupu. Chování algoritmu proto můžeme popsat rozhodovacím stromem. Vnitřní vrcholy stromu odpovídají porovnáním prvků, listy odpovídají vydaným permutacím. Ze stromu vynecháme větve, které nemohou nastat (například pokud už víme, že x1 < x3 a x3 < x6 , a přijde na řadu porovnání x1 s x6 , už je jasné, jak dopadne). Počet porovnání v nejhorším případě je roven hloubce stromu. Jak ji spočítat? Všimneme si, že pro každou z možných permutací na vstupu musí chod algoritmu skončit v jiném listu (jinak by existovaly dvě různé permutace, které lze setřídit týmiž prohozeními, což není možné). Strom tedy musí mít alespoň n! různých listů. Hloubka rozhodovacího stromu odpovídá počtu porovnání. My chceme dokázat, že porovnání musí být aspoň Ω(n log n). Lemmátko: Ternární strom hloubky k má nejvýše 3k listů. Důkazík: Uvažme ternární strom hloubky k s maximálním počtem listů. V takovém stromu budou všechny listy určitě ležet na poslední hladině (kdyby neležely, můžeme pod některý list na vyšší hladině přidat další dva vrcholy a získat tak „listnatějšíÿ strom stejné hloubky). Jelikož na i-té hladině je nejvýše 3i vrcholů, všech listů je nejvýše 3k . ♥ 2
2011-07-31
Z tohoto lemmátka plyne, že rozhodovací strom musí být hluboký alespoň log3 n!. Zbytek už je snadné cvičení z diskrétní matematiky: Lemmátko: n! p ≥ nn/2 . p Důkazík: n! p = (n!)2 =p 1(n − 1) · 2(n − 2) · . . . · n · 1, což můžeme také √ zapsat jako 1(n − 1)· 2(n − 2)·. . .· n · 1. Přitom pro každé 1 ≤ k ≤ n je k(n+1−k) = kn+k−k 2 = n+(k−1)n+k(1−k) = n+(k−1)(n−k) ≥ n. Proto je každá z odmocnin větší nebo rovna n1/2 a n! ≥ (n1/2 )n = nn/2 . ♥
Hloubka stromu tedy činí minimálně log3 n! ≥ log3 (nn/2 ) = n/2·log3 n = Ω(n log n), což jsme chtěli dokázat. ♥ Ukázali jsme si třídění v čase O(N log N ) a také dokázali, že líp to v obecném případě nejde. Naše třídící algoritmy jsou tedy optimální (až na multiplikativní konstantu). Opravdu? Překvapivě můžeme třídit i rychleji – věta omezuje pouze třídění pomocí porovnávaní. Co když o vstupu víme víc, třeba že je tvořen čísly z omezeného rozsahu. Counting sort Counting sort je algoritmus pro třídění N celých čísel s maximálním rozsahem hodnot R. Třídí v čase Θ(N + R) s paměťovou náročností Θ(R). Algoritmus postupně prochází vstup a počítá si ke každému prvku z rozsahu, kolikrát jej viděl. Poté až projde celý vstup, projde počítadla a postupně vypíše všechna čísla z rozsahu ve správném počtu kopií. Algoritmus: (třídění posloupnosti x1 , . . . , xN ∈ {1, . . . , R} pomocí Counting sort u) 1. 2. 3. 4. 5. 6. 7. 8. 9. 10.
Pro i = 1 . . . R opakujeme: pi ← 0 Pro i = 1 . . . N opakujeme: px i ← px i + 1 j←1 Pro i = 1 . . . R opakujeme: Pokud pi 6= 0: vj ← i j ←j+1 Vrátíme výsledek v1 , . . . , vN .
Přihrádkové třídění Counting sort nám moc nepomůže, pokud chceme třídit ne přímo celá čísla, nýbrž záznamy s celočíselnými klíči. Na ty se bude hodit přihrádkové třídění neboli Bucket-sort („kbelíkové tříděníÿ). Uvažujme opět N prvků s klíči v rozsahu 1, . . . , R. Pořídíme si R přihrádek P1 , . . . , PR , prvky do nich roztřídíme a pak postupně vypíšeme obsah přihrádek v pořadí podle klíčů. Potřebujeme k tomu čas Θ(N + R) a paměť Θ(N + R). Navíc se jedná o stabilní algoritmus. 3
2011-07-31
Algoritmus: (třídění prvků x1 , . . . , xn s klíči c1 , . . . , cn ∈ {1, . . . , R} pomocí bucketsort u) 1. P1 . . . PR ← ∅ 2. Pro i = 1 . . . n: 3. Vložíme xi do Pci . 4. Pro j = 1 . . . R 5. Vypišeme obsah Pj . Lexikografické třídění k-tic Mějme n uspořádaných k-tic prvků z množiny {1 . . . R}k . Úkol zní seřadit k-tice slovníkově (lexikograficky). Můžeme použít metodu rozděl a panuj, takže prvky setřídíme nejprve podle první souřadnice k-tic a pak se rekurzivně zavoláme na každou přihrádku a třídíme podle následující souřadnice. Nebo můžeme využít toho, že bucket-sort je stabilní a třídit takto: Algoritmus: (třídění k-tic x1 , . . . , xn lexikograficky pomocí Bucket-sortu) 1. S ← x1 , . . . , xn . 2. Pro i = k až 1 opakujeme: 3. S ← bucket-sort S podle i-té souřadnice. 4. Vydáme výsledek S. Pro přehlednost v následujícím pozorování označme ℓ = k − i + 1, což přesně odpovídá tomu, v kolikátém průchodu cyklu jsme. Pozorování: Po ℓ-tém průchodu cyklem jsou prvky uspořádány lexikograficky podle i-té až k-té souřadnice. Důkaz: Indukcí podle ℓ: • Pro ℓ = 1 jsou prvky uspořádány podle poslední souřadnice. • Po ℓ průchodech již máme prvky setříděny lexikograficky podle ité až k-té souřadnice a spouštíme (ℓ + 1)-ní průchod, tj. budeme třídit podle (i − 1)-ní souřadnice. Protože bucket-sort třídí stabilně, zůstanou prvky se stejnou (i − 1)-ní souřadnicí vůči sobě seřazeny tak, jak byly seřazeny na vstupu. Z IP tam však byly seřazeny lexikograficky podle i-té až k-té souřadnice. Tudíž po (ℓ + 1)-ním průchodu jsou prvky seřazeny podle (i − 1)-ní až k-té souřadnice.
♥ Časová složitost je Θ(k · (n + R)), což je lineární s délkou vstupu (k · n) pro pevné k a R; paměťová složitost činí Θ(n + R). Třídění čísel 1 . . . R podruhé (Radix sort) Zvolíme základ Z a čísla zapíšeme v soustavě o základu Z, čímž získáme (⌊logz R⌋ + 1)-tice, na které spustíme předcházející algoritmus. Díky tomu budeR me třídit v čase Θ( log log Z · (n + Z)). Jak zvolit vhodné Z? Pokud bychom zvolili Z konstantní, časová složitost bude Θ(log R·n), což může R α být n log n nebo i víc. Zvolíme-li Z = n, dostáváme Θ( log log n · n), což pro R ≤ n znamená O(αn). Polynomiálně velká celá čísla jde tedy třídit v lineárním čase. 4
2011-07-31
Třídění řetězců (Na přednášce letos nebylo, ale pro úplnost uvádíme.) Mějme n řetězců r1 , r2 . . . rn dlouhých l1 , l2 . . . ln Označme si L = max1≤i≤n li délku nejdelšího řetězce a R počet znaků abecedy. Problém je, že řetězce nemusí být stejně dlouhé (pokud by byly, lze se na řetězce dívat jako na k-tice, které už třídit umíme). S tím se můžeme pokusit vypořádat doplněním řetězců mezerami tak, aby měly všechny stejnou délku, a spustit na něj algoritmus pro k-tice. Tím dostaneme algoritmus, který bude mít časovou složitost O(Ln), což bohužel může být až kvadratické vzhledem k velikosti vstupu. Příklad: na vstupu mějme k řetězců, kde prvních k−1 z nich bude mít délku 1 a poslední řetězec bude dlouhý přesně k. Vstup má tedy celkovou délku 2k−1 a my teď doplníme prvních k −1 řetězců mezerami. Vidíme, že algoritmus teď bude pracovat v čase O(k 2 ). To, co nám nejvíce způsobovalo problémy u předchozího příkladu, bylo velké množství času zabraného porovnáváním doplněných mezer. Zkusíme proto řešit náš problem trochu chytřeji a koncové mezery do řetězů vůbec přidávat nebudeme. Nejprve roztřídíme bucket-sortem řetězce do přihrádek (množin) Pi podle jejich délek, kde i značí délku řetězců v dané přihrádce, neboli definujme Pi = {rj |lj = i}. Dále si zavedeme seznam setříděných řetězců S takový, že v něm po k-tém průchodu třídícím cyklem budou řetězce s délkou alespoň L−k+1 (označme l) a zároveň v něm tyto řetězce budou setříděny lexikograficky od l-tého znaku po L-tý. Z definice tohoto seznamu je patrné, že po L krocích třídícího cyklu bude tento seznam obsahovat všechny řetězce a tyto řetězce v něm budou lexikograficky seřazeny. Zbývá už jen popsat, jak tento cyklus pracuje. Nejprve vezme l-tou množinu Pl a její řetězce roztřídí do přihrádek Qj (kde index j značí j-tý znak abecedy) podle jejich l-tého (neboli posledního) znaku. Dále vezme seznam S a jeho řetězce přidá opět podle jejich l-tého znaku do stejných přihrádek Qj za již dříve přidané řetězce z Pl . Na závěr postupně projde všechny přihrádky Qj a řetězce v nich přesune do seznamu S. Protože řetězce z přihrádek Qj bude brát ve stejném pořadí, v jakém do nich byly umístěny, a protože ze seznamu S, který je setřízený podle (l + 1)-ního znaku po L-tý, bude také brát řetězce postupně, bude seznam S po k-tém průchodu přesně takový, jaký jsme chtěli (indukcí bychom dokázali, že cyklus pracuje skutečně správně). Zároveň z popisu algoritmu je jasné, že během třídění každý znak každého řetězce použijeme právě jednou, tudíž algoritmus bude lineární s délkou vstupu (pro úplnost dodejme, že popsaný algoritmus funguje v případech, kdy abeceda má pevnou velikost). Algoritmus: (třídění řetězců) 1. 2. 3. 4. 5. 6. 7.
L ← max(l1 , l2 , . . . , ln ) Pro i ← 1 do L opakuj: Pi ← ∅ Pro i ← 1 do n opakuj: pridej (Pli , ri ) S←∅ Pro i ← L do 1 opakuj: 5
2011-07-31
8. Pro j ← 1 do R opakuj: 9. Qj ← ∅ 10. Pro j ← 1 do velikost(Pi ) opakuj: 11. vezmi (Pi , r) 12. pridej (Qr[i] , r) 13. Pro j ← 1 do velikost(S) opakuj: 14. vezmi (S, r) 15. pridej (Qr[i] , r) 16. S←∅ 17. Pro j ← 1 do R opakuj: 18. Pro k ← 1 do velikost(Qj ) opakuj: 19. vezmi (Qj , r) 20. pridej (S, r) 21. výsledek S Časová složitost tohoto algoritmu tedy bude O(RN ), kde N je délka vstupu a R počet znaků abecedy. Zoo třídících algoritmů podruhé Doplňme tedy naši tabulku: InsertSort MergeSort HeapSort QuickSort BucketSort k-tice RadixSort
Čas Θ(n2 ) Θ(n log n) Θ(n log n) Θ(n log n) Θ(n + R) Θ(k(n + R)) Θ(n logn R)
Pomocná paměť Θ(1) Θ(n) Θ(1) Θ(log n) Θ(n + R) Θ(n + R) Θ(n)
Stabilní + + − − + + +
K čemu je vlastně třídění dobré? Díky němu můžeme rychle vyhledávat prvky v množině, konkrétně v čase O(log n) např. pomocí půlení intervalů. Dalším problémem, na který se hodí použít třídění, je zjištění, zda se v posloupnosti nějaké její hodnoty opakují. Dá se dokázat, že tuto úlohu nelze vyřešit lépe (rychleji), než tak, že hodnoty nejprve setřídíme a poté setříděnou posloupnost projdeme. Násobení matic n×n a Strassenův algoritmus Nejdříve si připomeneme definici násobení dvou čtvercových matic typu n × n. Platí, že prvek v i-tém řádku a j-tém sloupci výsledné matice Z se rovná standardnímu skalárnímu součinu i-tého řádku první matice X a j-tého sloupce druhé matice Y . Formálně zapsáno: Zij =
n X
k=1
Xik · Ykj .
6
2011-07-31
_j _i
(i,j)
=
X
X
Y
Z
Násobení matic Algoritmus, který by násobil matice podle této definice, by měl časovou složitost Θ(n3 ), protože počet prvků ve výsledné matici je n2 a jeden skalární součin vektorů dimenze n vyžaduje lineární počet operací. My se s touto časovou složitostí ovšem nespokojíme a budeme postupovat podobně jako při vylepšování algoritmu na násobení velkých čísel. Bez újmy na obecnosti předpokládejme, že budeme násobit dvě matice typu n × n, kde n = 2k , k ∈ . Obě tyto matice rozdělíme na čtvrtiny a tyto části postupně označíme u matice X písmeny A, B, C a D, u matice Y písmeny P , Q, R a S. Z definice násobení matic zjistíme, že čtvrtiny výsledné matice Z můžeme zapsat pomocí součinů částí násobených matic. Levá horní čtvrtina bude odpovídat výsledku operací AP + BR, pravá horní čtvrtina bude AQ + BS, levá dolní CP + DR a zbylá CQ + DS (viz obrázek).
N
A
P
B
Q
X
D
C X
AP+BR
AQ+BS
CP+DR
CQ+DS
=
R
S
Z
Y Násobení rozčtvrcených matic
Převedli jsme tedy problém násobení čtvercových matic řádu n na násobení čtvercových matic řádu n/2. Tímto rozdělováním bychom mohli pokračovat, dokud bychom se nedostali na matice řádu 1, jejichž vynásobení je triviální. Dostali jsme tedy klasický algoritmus typu rozděl a panuj. Pomohli jsme si ale nějak? V každém kroku provádíme 8 násobení matic polovičního řádu a navíc konstantní počet operací na n2 prvcích. Dostáváme tedy rekurentní zápis časové složitosti: n T (n) = 8T + Θ(n2 ). 2 Použitím Master Theoremu lehce dojdeme k závěru, že složitost je stále Θ(n3 ), tedy stejná jako při násobení matic z definice. Zdánlivě jsme si tedy nepomohli, ale stejně jako tomu bylo u násobení velkých čísel, i teď můžeme zredukovat počet násobení matic polovičního řádu, které nejvíce ovlivňuje časovou složitost algoritmu. Není to bohužel nic triviálního, a proto si raději rovnou řekneme správné řešení. 7
2011-07-31
Jedná se o Strassenův algoritmus, který redukuje potřebný počet násobení na 7, a ještě před tím, než si ukážeme, jak funguje, dokážeme si, jak nám to s časovou složitostí vlastně pomůže: T (n) = 7T
n 2
+ Θ(n2 ) =⇒ Θ(nlog2 7 ) = O(n2.808 ).
Výsledná složitost Strassenova algoritmu je tedy O(n2.808 ), což je sice malé, ale pro velké matice znatelné zlepšení oproti algoritmu vycházejícímu přímo z definice. Lemma: (vzorce pro násobení blokových matic ve Strassenově algoritmu)
A
B
C
D
!
·
P
Q
R
S
!
=
T1 + T4 − T5 + T7
T3 + T5
T2 + T4
T1 − T2 + T3 + T6
!
,
kde: T1 = (A + D) · (P + S)
T5 = (A + B) · S
T2 = (C + D) · P
T6 = (C − A) · (P + Q)
T3 = A · (Q − S)
T7 = (B − D) · (R + S)
T4 = D · (R − P ) Důkaz: Do čtverců 4×4 si napíšeme znaky + nebo − podle toho, jestli se při výpočtu dané matice přičítá nebo odečítá příslušný součin dvou matic. Řádky znamenají matice A, B, C a D a sloupce značí matice P , Q, R a S. Pokud se tedy v prvním řádku a prvním sloupci vyskytuje znak +, znamená to že přičteme součin matic A a P . Nejdříve si spočítáme pomocné matice T1 až T7 a z nich pak dopočítáme, co bude na příslušných místech ve výsledné matici.
+ · T1 = · +
· · · ·
· · · ·
+ · · +
· · T5 = · ·
· · T2 = + +
· · · ·
· · · ·
+ + · ·
· · · ·
· · · ·
· · · ·
· · T3 = · ·
- · · T6 = + + · · 8
· · · ·
· · · ·
+ · · ·
· · · ·
· · ·
· · T7 = · ·
· · T4 = · -
· · · ·
· · · ·
· · · +
· · · ·
· · ++ · · - 2011-07-31
+ · T1 + T4 − T5 + T7 = · ·
· · · ·
· + · ·
· · · = AP + BR ·
· · T3 + T5 = · ·
+ · · ·
· · · ·
· + · = AQ + BS ·
· · T2 + T4 = + ·
· · · ·
· · · +
· · · = CP + DR ·
· · T1 − T2 + T3 + T6 = · ·
· · + ·
· · · ·
· · · = CQ + DS +
Jak je vidět, výsledná matice je tvořena stejnými částmi jako při obyčejném násobení. Touto kapitolou jsme tedy dokázali následující větu: Věta: Strassenův algoritmus pro násobení matic n × n má časovou složitost v nejhorším případě O(n2.808 ). ♥ Poznámka: Zatím nejlepší dokázaný algoritmus má časovou složitost O(n2.376 ), leč s velkou multiplikativní konstantou. Dosažitelnost v grafech pomocí Strassenova algoritmu Matice mohou souviset s mnoha na první pohled nesouvisejícími problémy. (k) Lemma: Nechť A je matice sousednosti grafu, nechť Sz,j označíme počet sledů délky k z vrcholu j do vrcholu i. Pak S (k) = Ak . Důkaz: Indukcí podle k: • S (1) = A Pn P (k) (k) (k+1) • Si,j = z:(i,z)∈E(G) Sz,j = z=1 Ai,z Sz,j = (AS (k) )i,j
♥ Přidáním smyček do matice A zjistíme dostupnost vrcholů po cestách dlouhých k nebo kratších. Stačí tedy spočítat matici B = (A + E)k pro libovolné k ≥ n (E je jednotková matice). Pak Bi,j 6= 0 právě když existuje cesta z vrcholu i do vrcholu j. Pro vypočítání B nám stačí ⌈log n⌉ umocnění matice na druhou, což je speciální případ násobení matic. Časová složitost celého algoritmu tedy činí O(nlog2 7 · log n). Musíme však dávat pozor a normovat čísla (nulu necháme, nenulová nahradíme při každém násobení jedničkou), aby nám nepřerostla přes hlavu a hlavně přes maximální integer.
9
2011-07-31
