n log n est O(n)?

Je suis en train d'essayer de résoudre cette récurrence

T(n) = 3 T(n/2) + n lg n ..

Je suis arrivé à la solution qu'il appartient aux maîtres théorème de cas 2 puisque n lg n est O(n^2)

mais après en se référant à la solution manuelle, j'ai remarqué cette solution qu'ils ont

n log n est O(n)?

La soluttion dit que n lg n = O ( n ^(lg 3 - e)) e entre 0 et 0,58

cela signifie donc n lg n est O(n) .. est-ce vrai? Suis-je manqué quelque chose?

N'est pas nlgn O(n^2) ?

OriginalL'auteur Wael Awada | 2011-10-20

  1. 77

    C'est ce qui explique mieux les choses
    n log n est O(n)?

    merci pour l'effort .. Donc je suppose que n lg n > O(n) .. et le livre est mauvais?
    Le livre de la réponse n'est pas en contradiction O(n log n) > O(n).
    L'extrait du livre à l'air sous une forme écrite (si malheureux pour échanger des première et deuxième terme): Nous deux termes à prendre en compte pour en indiquant simple dominant fonctions: n lg n et n^logb un. Depuis n lg n est dominé par n à la puissance de rien plus, il est dominé par le n^lg 3.
    Avez-vous pris que graphique à partir d'ici? bigocheatsheet.com Vous devez créditer votre source!
    Il est Log2(100) ~ 7

    OriginalL'auteur Sreenath Nannat

  2. 14

    n*log(n) n'est pas O(n^2). Il est connu comme quasi-linéaire et il devient beaucoup plus lent que O(n^2). En fait n*log(n) est à moins de polynôme.

    En d'autres termes:

    O(n*log(n)) < O(n^k)

    où k > 1

    Dans votre exemple:

    3*T(2n) -> O(n^1.585)

    Depuis O(n^1.585) est polynomiale et domine O(n*log(n)), le dernier terme de baisse de donc à la finale de la complexité est O(n^1.585).

    Je pensais que le dernier terme diminue seulement quand il est plus .. donc en O(n + lg n) = O(n)
    Il a aussi tombe dans ce cas. Mais ça va prendre un exemple/analyse pour montrer pourquoi.

    OriginalL'auteur Mysticial

  3. 6

    nlg3 n'est pas O(n). Il finit en O(n)... En fait, tout exposant sur les n plus grand que 1 résultats dans un asymptotiquement plus de temps que O(n). Depuis lg(3) est d'environ 1.58, aussi longtemps que vous soustraire à moins de .58 de l'exposant, il est asymptotiquement plus de O(n).

    Donc, si je comprends bien, vous, comme moi, pensent que la solution manuelle est faux de dire n lgn = O(n)
    Non! n log n est plus grand, devient plus grand, et n'est PAS limité par n. C'est l'inverse.
    f(n) = O(g(n)) si f(n) < c.g(n) pour n > n0 .. donc si n lg n = O(n) quels sont les points c et n0 être ?
    Soit c = 1 et n0 5, et vous verrez que ce n'est PAS VRAI. L'autre manière autour.
    donc, si l'inverse est alors n = O(n lg n), où je comprends, mais le livre est en train de dire n lgn = O (n)

    OriginalL'auteur bdares