Loading web-font TeX/Math/Italic
Ask Your Question
0

Asymptotická složitost

asked Jan 9 '15

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.

add a comment

2 Answers

Sort by » oldest newest most voted
1

answered Jan 9 '15

Greg gravatar image

updated Jan 9 '15

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í...

link

Comments

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

Jasmes (Jan 9 '15)

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

Greg (Jan 9 '15)

Díky ;)

Marek Dostál (Jan 15 '15)
add a comment
0

answered Jan 10 '15

Ondřej Máca gravatar image

updated Jan 10 '15

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
link
add a comment

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: Jan 9 '15

Seen: 195 times

Last updated: Jan 11 '15