O (N log N) Complexité – Semblable à linéaire?

Je pense donc que je vais être enterré pour avoir posé une question aussi sortingviale mais je suis un peu confus à propos de quelque chose.

J’ai implémenté QuickSort en Java et en C et je faisais des comparaisons de base. Le graphique est apparu sous la forme de deux lignes droites, le C étant 4ms plus rapide que son homologue Java sur 100 000 nombres entiers aléatoires.

Résultats

Le code de mes tests peut être trouvé ici;

android-benchmarks

Je n’étais pas sûr de ce à quoi ressemblerait une ligne (n log n) mais je ne pensais pas que ce serait droit. 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.

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

Merci,

Gav

Agrandissez le graphique et vous verrez que O (n logn) n’est pas une ligne droite. Mais oui, le comportement est plutôt linéaire. Pour voir pourquoi, prenez simplement le logarithme de quelques très grands nombres.

Par exemple (base 10):

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

Ainsi, pour sortinger 1 000 000 de numéros, un sorting O (n logn) ajoute un facteur 6 (ou un peu plus, car la plupart des algorithmes de sorting dépendent des logarithmes de base 2). Pas beaucoup.

En fait, ce facteur de log est si petit que, pour la plupart des ordres de grandeur, les algorithmes O (n logn) établis surpassent les algorithmes de temps linéaires. Un exemple frappant est la création d’une structure de données de tableau de suffixes.

Un cas simple m’a récemment mordu lorsque j’ai essayé d’améliorer le sorting rapide des chaînes courtes en utilisant le sorting par base . Il s’avère que, pour les chaînes courtes, ce sorting à base de temps (linéaire) était plus rapide que le sorting rapide, mais il y avait un sharepoint basculement pour les chaînes encore relativement courtes, car le sorting de base dépend de la longueur des chaînes que vous sortingez.

FYI, le sorting rapide est en fait O (n ^ 2), mais avec un cas moyen de O (nlogn)

FYI, il y a une très grande différence entre O (n) et O (nlogn). C’est pourquoi il n’est pas limité par O (n) pour aucune constante.

Pour une démonstration graphique, voir:

O (n) vs O (nlogn)

Pour encore plus de plaisir dans une veine similaire, essayez de tracer le temps pris par n opérations sur la structure de données d’ensemble disjoint standard. Il a été montré qu’il est asymptotiquement n α ( n ) où α ( n ) est l’inverse de la fonction Ackermann (bien que votre manuel d’algorithmes habituel affichera probablement uniquement une limite de n log log n ou éventuellement n log * n ). Pour tout type de nombre que vous êtes susceptible de rencontrer comme taille d’entrée, α ( n ) ≤ 5 (et même log * n ≤ 5), même s’il approche asymptotiquement l’infini.

Ce que je suppose que vous pouvez apprendre de ceci est que si la complexité asymptotique est un outil très utile pour penser aux algorithmes, ce n’est pas tout à fait la même chose que l’efficacité pratique.

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

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

Astuce: 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)).

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

Wikipédia dit que Big-O est le pire des cas (c.-à-d. Que f (x) est égal à O (N) signifie que f (x) est “borné au-dessus” par N)

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

La dérivée de log (x) est 1 / x. C’est à quelle vitesse log (x) augmente à mesure que x augmente. Ce n’est pas linéaire, bien que cela puisse ressembler à une ligne droite car elle se plie 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 une constante, car toute puissance constante positive de N la dépassera éventuellement. Ce n’est pas exact à 100%, alors les professeurs seront en colère contre vous si vous l’expliquez ainsi.

La différence entre les logs de deux bases différentes est un multiplicateur constant. Recherchez la formule de conversion des 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 aura normalement quelques problèmes dans les données que vous tracez. Il y aura des différences dans les choses en dehors de votre programme (quelque chose qui change dans le cpu avant votre programme, les échecs du cache, etc.). Il faut beaucoup d’essais pour obtenir des données fiables. Les constantes sont le plus gros ennemi de l’application de la notation Big O à l’exécution réelle. Un algorithme O (N) avec une constante élevée peut être plus lent qu’un algorithme O (N ^ 2) pour assez petit N.

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

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

C’est là, mais c’est petit. C’est pourquoi O (nlog (n)) est tellement bon!