Comment calculer n log n = c

Question

J'ai un problème de devoirs pour ma classe d'algorithmes me demandant de calculer la taille maximale d'un problème qui peut être résolu dans un nombre donné d'opérations en utilisant un algorithme O (n log n) (c'est-à-dire: n log n = c). J'ai été capable d'obtenir une réponse approximative, mais y a-t-il un moyen propre d'obtenir une réponse exacte?

Answer 1

Il n'y a pas de formule fermée pour cette équation. En gros, vous pouvez transformer l'équation:

n log n = c 
log(n^n) = c 
    n^n = exp(c) 

Ensuite, cette équation a une solution de la forme:

n = exp(W(c)) 

où W est Lambert W function (voir en particulier "Exemple 2"). Il a été prouvé que W ne peut pas être exprimé en utilisant des opérations élémentaires. Toutefois, f(n)=n*log(n) est une fonction monotone. Vous pouvez simplement utiliser bissectrice (ici en python):

import math 

def nlogn(c): 
    lower = 0.0 
    upper = 10e10 
    while True: 
     middle = (lower+upper)/2 
     if lower == middle or middle == upper: 
      return middle 
     if middle*math.log(middle, 2) > c: 
      upper = middle 
     else: 
      lower = middle 

Answer 2

la notation O vous donne seulement le plus grand terme de l'équation. Par exemple, la performance de votre algorithme O (n log n) pourrait être mieux représentée par c = (n log n) + n + 53.

Cela signifie que sans connaître la nature exacte de la performance de votre algorithme, vous ne Ne pas être en mesure de calculer le nombre exact d'opérations nécessaires pour traiter une quantité donnée de données.

Mais il est possible de calculer que le nombre maximum d'opérations nécessaires pour traiter un ensemble de données de taille n est supérieur à un certain nombre, ou inversement que le plus gros problème peut être résolu, en utilisant cet algorithme et ce nombre des opérations, est inférieure à un certain nombre.

La notation O est utile pour comparer les 2 algorithmes, soit une O (n^2) algorithme est plus rapide qu'un O (n^3) algorithme etc.

voir Wikipedia pour plus d'informations.

some help with logs