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

Question

Donc je pense que je vais être enterré pour poser une question aussi banale mais je suis un peu confus à propos de quelque chose.

J'ai implémenté quicksort en Java et C et je faisais quelques comparissons de base. Le graphique est sorti comme deux droites, avec le C étant 4ms plus rapide que la contrepartie de Java plus de 100 nombres entiers aléatoires.

Le code pour mes tests peuvent être trouvés ici; ligne

android-benchmarks

Je ne savais pas quel (n log n) ressemblerait mais je ne pensais pas que ce serait simple. Je voulais juste vérifier que c'est le résultat attendu et que je ne devrais pas essayer de trouver une erreur dans mon code.

Je bloqué la formule dans Excel et pour la base 10, il 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

rendre le graphique plus grand et vous verrez que O (n log n) est pas tout à fait une ligne droite. Mais oui, c'est assez proche du comportement linéaire. Pour voir pourquoi, prenez juste le logarithme de quelques très grands nombres.

Par exemple (base 10):

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

Ainsi, pour trier 1.000.000 numéros, un O (n log n) tri ajoute un facteur measly 6 (ou juste un peu plus que la plupart des algorithmes de tri dépendent base 2 logarithmes). Pas énormément.

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

Un cas simple m'a récemment mordu when I tried to improve a quicksort sorting of short strings by employing radix sort. Il s'avère que, pour les chaînes courtes, ce type de base de temps (linéaire) était plus rapide que le tri rapide, mais il y avait un point de bascule pour les chaînes relativement courtes, puisque le tri radix dépend crucialement de la longueur des cordes que vous triez.

Answer 2

log (N) est (très) à peu près le nombre de chiffres à N. Ainsi, pour la plupart, il y a peu de différence entre log (n) et log (n + 1)

Answer 3

Essayez comploter une ligne linéaire réelle sur le dessus de celui-ci et vous verrez la petite augmentation. Notez que la valeur Y à 50,0000 est inférieure à la valeur 1/2 Y à 100 000.

Il est là, mais il est petit. C'est pourquoi O (nlog (n)) est si bon!

Answer 4

1. Habituellement, les algorithmes O (n * log (n)) ont une implémentation logarithmique à 2 bases.
2. Pour n = 1024, log (1024) = 10, alors n * log (n) = 1 024 * 10 = 10240 calculs, une augmentation d'un ordre de grandeur.Donc, O (n * log (n)) est similaire à linéaire seulement pour une petite quantité de données.

Conseil: n'oubliez pas que le tri rapide se comporte très bien sur les données aléatoires et qu'il ne s'agit pas d'un algorithme O (n * log (n)).

Answer 5

Pour encore plus de plaisir dans la même veine, essayez de tracer le temps pris par les opérations n sur la norme disjoint set data structure. Il a été asymptotiquement n   α (n) où α (n) est l'inverse de la Ackermann function (si votre manuel d'algorithmes habituels montrera probablement une limite de n log log n ou éventuellement n   log*   n). Pour tout type de numéro que vous serez susceptible de rencontrer la taille d'entrée, α (n)   ≤   5 (et même log *   n   ≤   5), bien qu'il ne l'infini approche asymptotiquement. Ce que je suppose que vous pouvez apprendre de ceci est que si la complexité asymptotique est un outil très utile pour penser à des algorithmes, ce n'est pas tout à fait la même chose que l'efficacité pratique.

Answer 6

Pour votre information, quicksort est en fait O (n^2), mais avec une moyenne de cas O (nlogn)

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

Pour voir de démonstration graphique:

Answer 7

Toutes les données peuvent être tracées sur une ligne si les axes sont choisis correctement :-)

Wikipedia dit Big-O est le pire des cas (-à-dire f (x) est O (N) des moyens de f (x) est "majorée" par N) https://en.wikipedia.org/wiki/Big_O_notation

Voici une belle série de graphiques illustrant les différences entre les diverses fonctions communes: http://science.slc.edu/~jmarshall/courses/2002/spring/cs50/BigO/

La dérivée de log (x) est 1/x. C'est ainsi que log (x) augmente rapidement lorsque x augmente. Ce n'est pas linéaire, bien que cela puisse ressembler à une ligne droite parce qu'elle se courbe si lentement. En pensant à O (log (n)), je pense à O (N^0 +), c'est-à-dire la plus petite puissance de N qui n'est pas constante, puisque toute puissance constante positive de N la dépassera finalement. Ce n'est pas exact à 100%, alors les professeurs vont se mettre en colère contre vous si vous l'expliquez de cette façon.

La différence entre les logs de deux bases différentes est un multiplicateur constant. Recherchez la formule pour convertir les journaux entre deux bases: (sous "changement de base" ici: https://en.wikipedia.org/wiki/Logarithm) L'astuce consiste à traiter k et b comme des constantes.

En pratique, il y a normalement des problèmes de hachage dans les données que vous tracez. Il y aura des différences dans les choses en dehors de votre programme (quelque chose d'échange dans l'unité centrale de traitement de votre programme, manquements de cache, etc.). Il faut beaucoup de courses pour obtenir des données fiables. Les constantes sont le plus grand ennemi de la tentative d'appliquer la notation Big O à l'exécution réelle. Un algorithme O (N) avec une constante haute peut être plus lent qu'un algorithme O (N^2) pour N assez petit.