n * log n et n / log n en fonction du temps d'exécution polynomial

Je comprends que est plus rapide que et plus lent que . Ce qui est difficile à comprendre pour moi, c'est comment comparer réellement et avec où .$\Theta(n)$$\Theta(n\log n)$$\Theta(n/\log n)$$\Theta(n \log n)$$\Theta(n/\log n)$$\Theta(n^f)$$0 < f < 1$

Par exemple, comment décidons-nous vs ou$\Theta(n/\log n)$$\Theta(n^{2/3})$$\Theta(n^{1/3})$

J'aimerais avoir des instructions pour procéder dans de tels cas. Je vous remercie.

Si vous dessinez simplement quelques graphiques, vous serez en bonne forme. Wolfram Alpha est une excellente ressource pour ces types d'enquêtes:

Généré par ce lien . Notez que dans le graphique, log (x) est le logarithme naturel, c'est pourquoi l'équation d'un graphique semble un peu drôle.

est l'inverse de 2 n . Tout comme 2 n croît plus rapidement que tout polynôme n k, quelle que soit la taille d'un k fini, log n croît plus lentement que toutes les fonctions polynomiales n k, quelle que soit la taille d'un k positif non nul.$\log n$$2^n$$2^n$$n^k$$k$$\log n$$n^k$$k$

vs n k , pour k < 1 est identique à: n / log n vs n / n 1 - $n / \log n$$n^k$$k < 1$$n / \log n$$n / n^{1-k}$

comme pour grand n , n / log n > n k pour k < 1 et grand n .$n^{1-k} > \log n$$n$$n / \log n > n^k$$k < 1$$n$

Pour de nombreux algorithmes, il arrive parfois que les constantes soient différentes, ce qui fait que l'une ou l'autre est plus rapide ou plus lente pour des tailles de données plus petites et n'est pas aussi bien ordonnée par la complexité algorithmique.

Cela dit, si l'on ne considère que les très grandes tailles de données, à savoir. que l'on gagne finalement, O(n^f)est alors plus rapide que O(n/log n)pour 0 < f < 1.

Une grande partie de la complexité algorithmique consiste à déterminer quel algorithme est finalement plus rapide, sachant ainsi que O(n^f)c'est plus rapide que O(n/log n)pour 0 < f < 1, c'est souvent suffisant.

Une règle générale est que la multiplication (ou la division) par log nsera finalement négligeable par rapport à la multiplication (ou la division) par n^fpour tout f > 0.

Pour le montrer plus clairement, considérons ce qui se passe lorsque n augmente.

   n       n / log n         n^(1/2)
   2        n/ 1              ?
   4        n/ 2             n/ 2
   8        n/ 3              ?
  16        n/ 4             n/ 4
  64        n/ 6             n/ 8
 256        n/ 8             n/16
1024        n/10             n/32

Remarquez ce qui diminue plus rapidement? C'est la n^fcolonne.

Même si elle fétait plus proche de 1, la n^fcolonne commencera juste plus lentement, mais lorsque n double, le taux de variation du dénominateur s'accélère, tandis que le dénominateur de la n/log ncolonne semble changer à un taux constant.

Tracons un cas particulier sur un graphe

Source: Wolfram Alpha

J'ai sélectionné O(n^k)tel qui kest assez proche de 1 (at 0.9). J'ai également sélectionné les constantes afin qu'au départ O(n^k)soit plus lent. Cependant, notez qu'il finit par "gagner" à la fin, et prend moins de temps que O(n/log n).

Pense juste à comme $n^f$ . Doncpour votre exemple,n2/3=n/n1/3. Il est ensuite facile de comparer la croissance de$\dfrac{n}{n^{1-f}}$$n^{2/3}=n/n^{1/3}$

$\log n$$n^\varepsilon$$\varepsilon>0$

Lors de la comparaison des temps d'exécution, il est toujours utile de les comparer en utilisant de grandes valeurs de n. Pour moi, cela aide à construire une intuition sur la fonction qui est la plus lente

Dans votre cas, pensez à n = 10 ^ 10 et a = 0,5

O(n/logn) = O(10^10/10) = O(10^9)
O(n^1/2) = O(10^10^.5) = O(10^5)

Par conséquent, O (n ^ a) est plus rapide que O (n / logn), lorsque 0 <a <1, j'ai utilisé une seule valeur, cependant, vous pouvez utiliser plusieurs valeurs pour créer une intuition sur la fonction

$f \prec g$

$(2, 10) < (3, 5)$$(2, 10) > (2, 5)$

Appliqué à votre exemple:

$\mathcal{O}(n/\log n) \Rightarrow (1, -1, 0)$

$\mathcal{O}(n^{2/3}) \Rightarrow (2/3, 0, 0)$

$\mathcal{O}(n^{1/3}) \Rightarrow (1/3, 0, 0)$

Vous pourriez dire: les pouvoirs de n dominent les pouvoirs de log, qui dominent les pouvoirs de log log.

Source: Mathématiques concrètes, p. 441