Rozděl a panuj Hanojské věže ► Jak (rekurzivně) vyřešit? ► Kolik kroků (přesně) je třeba vykonat? Rozděl a panuj Násobení čísel Máme na vstupu dvě nbitová čísla x a y a chceme je vynásobit. Časovou složitost počítáme jako počet bitových operací. ► Jak složité je násobení dvou čísel „školním" algoritmem? Rozděl a panuj Násobení čísel Máme na vstupu dvě nbitová čísla x a y a chceme je vynásobit. Časovou složitost počítáme jako počet bitových operací. ► Jak složité je násobení dvou čísel „školním" algoritmem? ► Jak bychom mohli použít princip Rozděl a panufi Rozděl a panuj Násobení čísel Máme na vstupu dvě nbitová čísla x a y a chceme je vynásobit. Časovou složitost počítáme jako počet bitových operací. ► Jak složité je násobení dvou čísel „školním" algoritmem? ► Jak bychom mohli použít princip Rozděl a panufi Pokud rozdělíme čísla na poloviny (bitového zápisu), pak máme: x = 2m • xL + xR y = 2m • yL + yR kde m = \n/2 a součin x • y můžeme spočítat jako: 22m • xL • yL + 2m • (x/_ • yR + xR • yL) + xR • yR ► Jakou má toto rekurzivní řešení složitost? ► Jak to můžeme vylepšit? Master Theorem (pro připomenutí) Pokud T(n) < a ■ T(\n/b]) + 0(nd) pro nějaká a > 1, b > 1 a d>0, pak C 0(nd) a bd Rozděl a panuj Počítání mocniny Chceme počítat mocninu bk, kde k je přirozené číslo (včetně 0) a b je libovolný objekt, který umíme násobit (přirozené číslo, reálné číslo, čtvercová matice). Složitost budeme počítat jako počet operací násobení. ► Triviální řešení používá O(k) operací násobení. Zvládnete to lépe pomocí techniky Rozděl a panufi Rozděl a panuj Rozbíjení džbánů Máme žebřík s n příčkami a máme k dispozici k džbánů. Chceme zjistit, jaká je nejvyšší bezpečná příčka. Bezpečná příčka je taková, že džbán z ní hozený se nerozbije. Kolik nejméně pokusů (hodů) je třeba učinit? 1. Předpokládejme, že k = 1. Rozděl a panuj Rozbíjení džbánů Máme žebřík s n příčkami a máme k dispozici k džbánů. Chceme zjistit, jaká je nejvyšší bezpečná příčka. Bezpečná příčka je taková, že džbán z ní hozený se nerozbije. Kolik nejméně pokusů (hodů) je třeba učinit? 1. Předpokládejme, že k = 1. 2. Předpokládejme, ze k = 2. Rozděl a panuj Rozbíjení džbánů Máme žebřík s n příčkami a máme k dispozici k džbánů. Chceme zjistit, jaká je nejvyšší bezpečná příčka. Bezpečná příčka je taková, že džbán z ní hozený se nerozbije. Kolik nejméně pokusů (hodů) je třeba učinit? 1. Předpokládejme, že k = 1. 2. Předpokládejme, ze k = 2. 3. Jak by vypadalo řešení pro obecné kl Rozděl a panuj Souvislá podposloupnost s největším součtem Máme na vstupu posloupnost celých čísel. Chceme najít souvislou podposloupnost této posloupnosti, která má co největší součet. Příklad: Pro vstup 3, -5, 7, 0, -2, 6, 8, -9, 3 je řešením souvislá podposloupnost 7, 0, -2, 6, 8 (součet 19). ► Jak zde použít techniku Rozděl a panuji ► Jakou složitost má vaše řešení?