Pourquoi la séquence suivante des fonctions commandées par asymptotique des taux de croissance?

Ordonner les expressions suivantes dans l'accroissement de la Θ-commande. Si les deux fonctions sont du même ordre de croissance, vous devez l'état de ce fait.

n log n, n-1, log n, nlog n, 10n + n3/2, πn, 2n, 2log n, 22log n, log n!

Quelqu'un peut m'expliquer pourquoi la réponse suivante est-elle correcte?

n-1 ≪ log n ≪ 2log n ≪ n log n = log n! ≪ 10n + n3/2≪ nlog n ≪ 2n = 22log n ≪ πn

OriginalL'auteur patric | 2012-03-03

  1. 6

    Vous devez utiliser les faits que:

    lim(n->∞) f(n)/g(n) = 0  this gives you Θ(f(n)) < Θ(g(n))
lim(n->∞) f(n)/g(n) = c; c > 0 this gives you Θ(f(n)) = Θ(g(n))
lim(n->∞) f(n)/g(n) = ∞  this gives you Θ(f(n)) > Θ(g(n))

    Maintenant à l'aide que vous obtenez:

    lim(n->∞) n^−1 /log n = lim(n->∞) 1 /(n * log n) = 0.

    Cela vous donne immédiatement Θ(n^−1) < Θ(log n)

    Aller avec le reste.

    Pour certains calculs, vous pourriez trouver L'Hôpital de la règle utile.

    OriginalL'auteur Boris Strandjev

  2. 2

    Ainsi, il a été un long temps depuis que j'ai pensé à ces concepts (et je suis sûr que d'autres me corriger si c'est faux) mais je ne suis pas d'accord avec votre réponse. Tout d'abord thêta moyens liés au-dessus et au-dessous de par cette fonction. Cela signifie 10n + n3/2, 2n, et nn sont tout de même thêta classe. journal n, 2log n, 22log n sont également toutes de la même classe. De voir que n log n est de la même classe que log n! utilisation stirling rapprochement. Ainsi, vous bénéficiez de:

    log n = 2 log n = 22 log n ≪ n−1 = 10n + n3/2 = 2n = πn ≪ n log n = log n!

    Maintenant, si 'n3/2" signifie n^(3/2) plutôt que de 3/2*n alors la commande serait:

    log n = 2 log n = 22 log n ≪ n−1 = 2n = πn ≪ n log n = log n! ≪ 10n + n3/2
    N'n3/2 moyenne n à la puissance de 1,5? Si oui, ne serait pas 10n + n3/2 et 2n être différente de la classe? n - 1 devrait certainement être à 2n et nn
    oh, je l'ai pris à la moyenne n * 3/2... si il est n^(3/2) alors que serait entre nn et n log n
    Correct. Pour tous les n >= 2, nous avons n-1 <= n <= 2*(n-1), donc c'est là où il appartient. Si n3/2 était censé être n^(3/2), qui serait la plus forte croissance de ces.
    vous avez raison monsieur, mon erreur... comme je l'ai dit, il a été un moment
    merci, il y a une erreur avec les pouvoirs, j'ai corrigé cela, mais je vais soumettre de nouveau afin d'obtenir des réponses correctes

    OriginalL'auteur hackartist