Matematické Fórum

Moonchild · 05. 12. 2012 02:45

Ahoj, mohl by mi prosím někdo poradit? Zasekl jsem se a nevím, jak dál. (Doufám, že jsem vložil příspěvek do správné sekce. Našel jsem tu nějakou sekci s diskrétní matematikou, ale pochopil jsem to tak, že je pro VŠB)

Mám za úkol odhadnout složitost $t(n) = 8t(\frac{n}{2})+n^{2}log(n)$ a odhad dokázat pomocí substituční metody.

Pomocí master theorem mi vyšlo :
$a = 8, b = 2, n^{log_2(8)}=n^{3}$
$\exists \varepsilon : n^{2}log(n) = O(n^{3+\varepsilon })$
z čehož jsem odvodil výsledek $\Theta (n^{3})$

V substituční metodě se snažím nejdříve ověřit, že platí $t(n) \le cn^{3}, c > 0$
Dosadil jsem: $t(n) \le 8c(\frac{n}{2})^{3}+n^{2}log(n)$
$t(n) \le cn^{3}+n^{2}log(n)$

A pokud jsem správně pochopil přednášku, tak musím "zlepšit odhad o aditivní konstantu", takže upravuji na
$t(n) \le cn^{3} - bn, b > 0$ :
Po dosazení a zkrácení:
$t(n) \le cn^{3} - 4bn + n^{2}log(n)$

A tady bohužel nevím, co dál. Vím, že následně budu ještě ověřovat t(n) >= cn^3, ale nevím, jak dokončit toto ověření. Nejsem si moc jistý tou aditivní konstantou, možná jsem to špatně pochopil. Budu vděčný za jakoukoliv pomoc. Děkuji

Matematické Fórum

#1 05. 12. 2012 02:45

Rekurentní rovnice - substituční metoda

Zápatí