(log(n))^log(n) et n/log(n), qui est plus rapide?

f(n)=(log(n))^log(n)

g(n)= n/log(n)

f = O(g(n))?

Réponse courte: Oui. Plus de réponse, exécuter un profiler sur le code. big-o n'est pas utilisable pour des mesures de performances réelles, seulement pour "ce qui se passe si N augmente vers l'infini" type de problèmes. Et ce n' "O(x)" ont à voir avec le problème? si f=O(g(n)), est n une constante? Si non, pourquoi n'est-il pas f(n)=O(g(n))? Ou est f liées à f(n)=(log(n))^log(n)?
si c'est les devoirs l'utilisation de la balise homework
stackoverflow.com/questions/2307283/...
Le Big O la notation n'est pas sur la vitesse mais sur la limitation de comportement.
Je ne savais pas que O() est équivalent à la mfr(), soit, et toujours associés avec mesure de la performance. Est-ce une notation commune en anglais?

OriginalL'auteur Soup | 2010-04-30

  1. 10

    Prendre le journal des deux côtés:

    log(f(n)) = log(log n) * log n

    log(g(n)) = log(n) - log(log(n)) = log(n)(1 - log(log(n))/log(n))

    Clairement log(log(n)) domine (1 - log(log(n))/log(n)), donc g est O(f). f n'est pas O(g). Puisque c'est les devoirs, vous devrez remplir dans les détails.

    Il est aussi assez facile d'obtenir une idée de ce que la réponse devrait être juste de l'essayer avec un grand nombre. 1024 est de 2^10, donc, en prenant n=1024:

    f(n) = 10^10

    g(n) = 1024/10.

    Évidemment ce n'est pas une preuve, mais je pense que l'on peut voir qui est en train de gagner cette course.

    OriginalL'auteur Steve Jessop

  2. 5

    f(n) croît plus rapidement que la g(n) si et seulement si f(en) aussi croît plus rapidement que la g en) depuis exp est strictement croissante à l'infini (le prouver à vous-même).

    Maintenant f(en) = nn et g en) = en /n, et vous pouvez citer les résultats connus.

    Ce n'est pas tout à fait droit. 1 - 1/x est strictement croissante, mais il ne s'ensuit pas que si f croît strictement plus vite que g, alors 1 - 1/f croît strictement plus rapide que 1 - 1/g. Ils peuvent se développer à la même big-O (sans surprise, puisqu'1 - 1/x converge vers une constante). Si votre résultat est vrai, mais pas pour les raisons invoquées.
    et seulement si" (2) nous Vous conseillons de comparer f(1 - 1/x), 1 - 1/f(x).
    OK, donc avec f(n) = n^2, g(n) = n. 1 - 1/n^2, (1 - 1/n)^2, et 1 - 1/n sont tous les O(1), de sorte qu'ils ne poussent pas (strictement) plus vite, même si certains d'entre eux sont strictement plus grand que les autres (pour n > 1). exp est "mieux" pour nos fins que juste strictement croissante, et prouve davantage sur les résultats.
    +1, alors. Vous n'avez même pas besoin de cette exp est strictement croissante, c'est juste que elle et son inverse les deux tendent vers l'infini. Je pense que.
    exp est convexe

    OriginalL'auteur kennytm

  3. 0

    Si la Limite[f[x] /g[x], x -> Infini] = Infini, alors f[x] croît plus vite que g[x].

    Limite[Log[x] ^ Log[x] /(x /Log[x]), x -> Infini] = + Infini

    Ainsi, le Journal[x] ^ Log[x] croît plus vite que x /Log[x]

    Si vous avez Mathematica, vous pouvez utiliser de l'Intrigue[Log[x]^(Log[x])/(x/Log[x], {x, 0, 100}] pour le voir.
    wolframalpha.com/input/...

    OriginalL'auteur yassin

  4. 0

    Mathematica donne la limite de f(n) /g(n) comme n tend vers l'infini l'infini, ce qui signifie que f se développe plus vite. Cela signifie que g(n) belongs to (=) O(f(n)).

    Vous pouvez utiliser cette par exemple, si vous n'avez pas de Mathematica.

    OriginalL'auteur IVlad

  5. 0

    f est beaucoup plus importante. Par n^loglog(n) -1 . log n

    OriginalL'auteur Fakrudeen