navigation
hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
|
courses:a4m01tal:ukol1_ls1314 [2014/03/11 23:44] tivvit [Řešení] |
courses:a4m01tal:ukol1_ls1314 [2025/01/03 18:28] (aktuální) |
||
|---|---|---|---|
| Řádek 24: | Řádek 24: | ||
| 4) Tady Master Theorem nejspíš použít nejde (ačkoliv jsem viděl podobné příklady, kde to nějak ohackovali a Master Theorem použili, ale moc jsem to nepobral). | 4) Tady Master Theorem nejspíš použít nejde (ačkoliv jsem viděl podobné příklady, kde to nějak ohackovali a Master Theorem použili, ale moc jsem to nepobral). | ||
| Tady se chce asi použít třeba ta "metoda" rekurzivních stromů z přednášky. Snažil jsem se to udělat jako v příkladech z přednášky, vyjádřil jsem součet přes celý strom (tj. tu složitost) pomocí geometrické posloupnosti (počet jejích členů je log2(n) - tedy lg(n), protože n se dělí vždy 2) a pak jí sečetl přes známý vzoreček pro součet. Vyšlo mi to O(n^2), jestli je to dobře nevím. | Tady se chce asi použít třeba ta "metoda" rekurzivních stromů z přednášky. Snažil jsem se to udělat jako v příkladech z přednášky, vyjádřil jsem součet přes celý strom (tj. tu složitost) pomocí geometrické posloupnosti (počet jejích členů je log2(n) - tedy lg(n), protože n se dělí vždy 2) a pak jí sečetl přes známý vzoreček pro součet. Vyšlo mi to O(n^2), jestli je to dobře nevím. | ||
| + | |||
| + | Lze řěšit přes Master Theorem (první pravidlo), ale vyšlo ti to dobře O(n^2) | ||
| 5) Předpoklad je špatně? Ta suma je aritmetická posloupnost, když si podle známého vzorečku na součet spočteme její součet, zjistíme že je to (n+n^2)/2, což je O(n^2) a ne O(n). | 5) Předpoklad je špatně? Ta suma je aritmetická posloupnost, když si podle známého vzorečku na součet spočteme její součet, zjistíme že je to (n+n^2)/2, což je O(n^2) a ne O(n). | ||
| + | |||
| Podle mě je špatně to vyhodnocení té indukce, protože ten krok n+1 má složitost O(1) takže je to O(n) + O(1) = O(n + 1) a konstantu zanedbáme. | Podle mě je špatně to vyhodnocení té indukce, protože ten krok n+1 má složitost O(1) takže je to O(n) + O(1) = O(n + 1) a konstantu zanedbáme. | ||
| ~~DISCUSSION~~ | ~~DISCUSSION~~ | ||
