Complexité O(N log N) - Similaire au linéaire ?

Question

Je pense que je vais me faire enterrer pour avoir posé une question aussi triviale, mais je suis un peu confus à propos de quelque chose.

J'ai implémenté quicksort en Java et en C et je faisais quelques comparaisons de base. Le graphique se présente sous la forme de deux lignes droites, le C étant 4 ms plus rapide que le Java sur 100 000 entiers aléatoires.

Le code de mes tests se trouve ici ;

Bancs d'essai Android

Je n'étais pas sûr de ce à quoi ressemblerait une ligne (n log n) mais je ne pensais pas qu'elle serait droite. Je voulais juste vérifier que c'est le résultat attendu et que je ne dois pas essayer de trouver une erreur dans mon code.

J'ai entré la formule dans Excel et pour la base 10, cela semble être une ligne droite avec un coude au début. Est-ce parce que la différence entre log(n) et log(n+1) augmente linéairement ?

Merci,

Gav

Answer 1

Agrandissez le graphique et vous verrez que O(n logn) n'est pas tout à fait une ligne droite. Mais oui, elle est assez proche d'un comportement linéaire. Pour comprendre pourquoi, il suffit de prendre le logarithme de quelques très grands nombres.

Par exemple (base 10) :

log(1000000) = 6
log(1000000000) = 9
…

Ainsi, pour trier 1 000 000 de nombres, un tri O(n logn) ajoute un minuscule facteur 6 (ou juste un peu plus puisque la plupart des algorithmes de tri dépendront des logarithmes de base 2). Ce n'est pas énorme.

En fait, ce facteur logarithmique est donc extraordinairement petit que pour la plupart des ordres de grandeur, les algorithmes établis en O(n logn) surpassent les algorithmes en temps linéaire. Un exemple frappant est la création d'une structure de données de type tableau de suffixes.

Un cas simple m'a récemment piqué lorsque j'ai essayé d'améliorer un tri quicksort de chaînes courtes en utilisant le tri radix. . Il s'est avéré que pour les chaînes courtes, ce tri radix (en temps linéaire) était plus rapide que le quicksort, mais il y avait un point de basculement pour les chaînes encore relativement courtes, puisque le tri radix dépend essentiellement de la longueur des chaînes que vous triez.

Answer 2

Pour info, quicksort est en fait O(n^2), mais avec un cas moyen de O(nlogn)

Pour info, il y a une différence assez importante entre O(n) et O(nlogn). C'est pourquoi il n'est pas bornable par O(n) pour toute constante.

Pour une démonstration graphique, voir :

Answer 3

Pour vous amuser encore plus dans la même veine, essayez de tracer le temps pris par n opérations sur la norme structure de données d'ensembles disjoints . Il a été démontré qu'il est asymptotiquement n  α( n ) où α( n ) est l'inverse de la Fonction d'Ackermann (bien que votre manuel d'algorithme habituel ne montre probablement qu'une limite de n journal de bord n ou éventuellement n   log*   n ). Pour tout type de nombre que vous serez susceptible de rencontrer comme taille d'entrée, α( n ) ≤ 5 (et en effet log*  n  ≤ 5), bien qu'elle se rapproche asymptotiquement de l'infini.

Je suppose que vous pouvez en tirer la leçon suivante : si la complexité asymptotique est un outil très utile pour réfléchir aux algorithmes, elle n'est pas tout à fait la même chose que l'efficacité pratique.

Answer 4

1. Habituellement, les algorithmes O( n*log(n) ) ont une implémentation logarithmique à base 2.
2. Pour n = 1024, log(1024) = 10, donc n*log(n) = 1024*10 = 10240 calculs, soit une augmentation d'un ordre de grandeur.

Ainsi, O(n*log(n)) est similaire à linéaire seulement pour une petite quantité de données.

Conseil : n'oubliez pas que quicksort se comporte très bien sur des données aléatoires et que ce n'est pas un algorithme O(n*log(n)).

Answer 5

Log(N) est (très) approximativement le nombre de chiffres dans N. Ainsi, dans la plupart des cas, il y a peu de différence entre log(n) et log(n+1).