Revision history [back]

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 +1}) $$

Snad jsem nic nepřehlédl. Zkusil jsem si to otestovat a vychází...

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 +1}) \mathcal{O}(2^n) $$

Snad jsem nic nepřehlédl. Zkusil jsem si to otestovat a vychází...