asked 2015-01-09 13:18:34 +0100
Ahoj, můžete mi prosím někdo poradit, jak se dá odhadnout složitost u tohoto příkladu?
j=1;
for (i=1 to n)
l=i;
j*=2;
while (l<j)
f();
l++
Výsledek má být $O(2^{n+1})$ podle fitwiki.
answered 2015-01-09 14:59:29 +0100
Přepsáno do (aspoň pro mě) pohodlnějšího tvaru máme algoritmus:
j = 1;
for (i = 1; i <= n; i++) {
j *= 2;
for(l = i; l < j; l++)
f();
}Ten si lze zjednodušit na kód se složitostí $ 2^{n +1} -2 $, kde $ l $ jde klasicky od nuly. $ n+1$ protože část s j *= 2; je ještě před tím vnitřním cyklem. A to odečítání dvojky je tam jen pro korekci, aby mi to vycházelo :-).
j = 1;
for (i = 1; i <= n; i++) {
j *= 2;
for(l = 0; l < j; l++)
f();
}Na horní odhad by to stačilo, ale na ověření správnosti výpočtu je ještě potřeba zjistit, kolik těch vnitřních iterací vynecháme. A vychází to přesně na známou aritmetickou řadu $1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}$, takže výsledná složitost je $$ 2^{n +1} - 2 - \frac{n(n+1)}{2} = \mathcal{O}(2^n) $$
Snad jsem nic nepřehlédl. Zkusil jsem si to otestovat a vychází...
answered 2015-01-11 00:15:33 +0100
Mě přijde užitečné zkusit si vypsat, jak to vychází pro prvních pár členů. Je to z toho lépe vidět.
i j f()
1 2 1
2 4 2
3 8 5
4 16 12
5 32 27
Asked: 2015-01-09 13:18:34 +0100
Seen: 195 times
Last updated: Jan 11 '15
Copyright students of FIT CTU and others, 2014. Content on this site is licensed under a Creative Commons Attribution-ShareAlike 4.0 International license.