Ask Your Question
0

Asymptotická složitost

asked 2015-01-09 13:18:34 +0100

Marek Dostál gravatar image

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.

edit retag flag offensive close delete

2 Answers

Sort by » oldest newest most voted
1

answered 2015-01-09 14:59:29 +0100

Greg gravatar image

updated 2015-01-09 18:24:43 +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í...

edit flag offensive delete publish link more

Comments

Jen podotknu, ze pripadny vysledek je $O(2^n)$, konstanty se zanedbavaji.

Jasmes ( 2015-01-09 18:21:44 +0100 )edit

Upraveno, nějak jsem to tam předtím bezmyšlenkovitě plácl...

Greg ( 2015-01-09 18:25:57 +0100 )edit

Díky ;)

Marek Dostál ( 2015-01-15 15:14:06 +0100 )edit
0

answered 2015-01-11 00:15:33 +0100

Ondřej Máca gravatar image

updated 2015-01-11 00:48:26 +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
edit flag offensive delete publish link more

Your answer

Please start posting your answer anonymously - your answer will be saved within the current session and published after you log in or create a new account. Please try to give a substantial answer, for discussions, please use comments and please do remember to vote (after you log in)!

Add answer

[hide preview]

Question tools

Follow
1 follower

Stats

Asked: 2015-01-09 13:18:34 +0100

Seen: 195 times

Last updated: Jan 11 '15