Est O(n^2) de plus qu'en O (n^2)logn)

Est O(n^2) est supérieure à O(n^2 log n) ?

Si oui ? comment ?

Peut-on avoir un exemple simple pour cela.

Aussi ,

Qu'est-ce que la complexité du code ci-dessous. 

int unknown(int n){
   int i,j,k=0;
   for(i=n/2;i<=n;i++){
     for(j=2;j<=n;j=j * 2){
         k =k + n/2;
     }
  }
return k;
}

et qu'est-Ce que la complexité de la valeur de retour k ?

Ce serait peut-être plus adapté à programmers.stackexchange.com
(n^2)logn ou n^(2logn) ?
les sons comme des devoirs...
Mitch Blé : (n^2)logn

OriginalL'auteur Nagesh Salunke | 2013-02-12

  1. 12

    O(n^2) est un sous-ensemble de O((n^2) * log(n)), et donc le premier est "mieux", il est facile de voir que, depuis log(n) est une fonction croissante, en multipliant quelque chose avec elle, vous obtenez un "plus" en fonction de l'origine (f(n) <= f(n) * log(n) pour chaque augmentation non négatif f et n>2)

    Le code snap vous a donné est O(nlog(n)), depuis l'intérieur de la boucle se répète log(n) fois par boucle externe itération, et la boucle externe répète n/2 fois - ce qui vous donne n/2 * log(n) qui est en O(nlog(n))

    OriginalL'auteur amit

  2. 2

    Ln(e) == 1, donc quelque chose de plus grand que e (~2,7) va donner Ln(n) > 1.

    Donc pour tout n, où n > e, O(n^2 ln(n)) > O(N^2)

    OriginalL'auteur Matthew Watson

  3. 0

    Je suppose que tu veux dire O((n^2) * log n), mais la réponse est la même et ce que vous devez prouver est fondamentalement la même, si c'est n^(2 * log n). Je vais en outre envisager de non-négatif fonctions, pour sauver un peu vous embêter avec des valeurs absolues.

    La réponse est que O(n^2) est un sous-ensemble strict de O((n^2) * log n). Il est plus petit.

    D'abord prouver qu'il est un sous-ensemble: Supposons que f est O(n^2). Ensuite, il existe M et k tel que pour tout n >= M, f(n) <= k(n^2).

    Laisser L = max(M, e) (où e est la base logarithmique). Alors pour tous les n >= L, log(n) >= log(e) == 1 (depuis n >= 1) et f(n) <= k(n^2) (depuis n >= M).

    Donc pour tous les n >= L, f(n) <= k(n^2) * log(n). Donc f est dans O((n^2) * log n).

    Deuxième, prouver qu'il est un sous-ensemble strict: laissez g la fonction g(n) = (n^2) * log n, donc g est dans O((n^2) * log n).

    Pour tout k, prendre L = e^k. Alors pour tout n > L, log(n) > k et donc g(n) > n^2 * k.

    Donc g n'est pas dans O(n^2), car il ne peut pas exister M et k tel que pour tout n >= M, g(n) <= k * n^2.

    Certainement que devrait être (2 + log n) au lieu de (2 * log n)?
    ce qui devrait être 2 + log n? Si la question est "mauvais", alors vous aurez à prendre avec l'interlocuteur, mais la question n'est certainement pas à dire 2 + log n.
    Vous êtes en train de dire que "(n^2) * log n" est "essentiellement la même que n^(2 * log n)", ce dernier devrait probablement être "(2 + log n)".
    Je suis en train de dire que ce que vous avez besoin de le prouver est fondamentalement la même. Les fonctions sont différentes. La forme de la preuve sera très similaire, mais avec des choix différents de L. La raison pour laquelle je mentionne n^(2 * log n) est tout simplement que ce que la question dit, n^2logn, est ambigu. Pour ma réponse, je suis allé avec la mise entre crochets dans le titre.

    OriginalL'auteur Steve Jessop