recherche binaire a une performance moyenne des affaires comme O(log n) et tri rapide avec O(n log n) est O(n log n) est identique à O (n) + O (log n)Comment visualisez-vous la différence entre O (log n) et O (n log n)?
C'est 6,7 milliards d'entrées. O (log n) est une recherche sur une colonne indexée (par exemple une clé primaire). O (n log n) renvoie la population entière dans l'ordre trié sur une colonne non indexée.
Une autre façon de l'imaginer:
log n est proportionnel au nombre de chiffres n.
n log n est n fois supérieure. Essayez d'écrire le numéro 1000 une fois plutôt que de l'écrire un millier de fois. La première prend le temps O (log n), la seconde prend l'heure O (n log n).
Maintenant, essayez à nouveau avec 6700000000. L'écrire une fois est encore trivial. Maintenant, essayez de l'écrire 6,7 milliards de fois. Même si vous pouviez l'écrire une fois par seconde, vous seriez mort avant la fin.
Non, O(n log n) = O(n) * O(log n)
En mathématiques, lorsque vous avez une expression (c.-à-d. e = mc^2), s'il n'y a pas d'opérateur, alors vous multipliez.
Normalement, la façon de visualiser O (n log n) est "faire quelque chose qui prend log n calculs n fois."
Si vous aviez un algorithme qui a d'abord itérer sur une liste, puis a fait une recherche binaire de cette liste (qui serait N + log N) vous pouvez exprimer que simplement O(n) parce que le n Nains du log n pour les grandes valeurs de n Imaginez une base de données avec chaque personne dans le monde.
Que signifie «O (n) * O (log n)»? – mquander
prendre une fonction de la classe O (n), et une autre fonction de la classe O (log n), la fonction résultante est dans la classe O (n log n). C'est ce que l'on entend par O (n) * O (log n) = O (n log n) – Phil
oups je voulais dire "les multiplier ensemble" en disant "résultat" – Phil
Vous pouvez le visualiser dans un complot, voir here par exemple:
À propos de la meilleure façon de visualiser est d'utiliser la vision. Bien joué. –
Génial. Merci d'avoir signalé cette ressource. J'ai utilisé Wolfram pour tracer 4 types communs de complexité computationnelle discutés dans la semaine 3 du cours CS50 de Harvard. http://www.wolframalpha.com/input/?i=plot+log(n)+vs+n+vs+n%2Alog(n)+vs+n%5E2+from+1+to+10 https: //www.youtube.com/embed/IM9sHGlYV5A – squarecandy
Une parcelle (log n) augmente, mais est concave vers le bas, ce qui signifie:
Une parcelle (n log n) augmente, et est (légèrement) concave vers le haut, ce qui signifie:
Dépend de si vous avez tendance à visualiser n comme ayant une va concrète Lue.
Si vous avez tendance à visualiser n comme ayant une valeur concrète, et les unités de f(n) sont temps ou instructions, O(log n) est n fois plus rapide que O(n log n) pour une tâche donnée de taille n. Pour les unités de mémoire ou d'espace, O(log n) est n fois plus petit pour une tâche donnée de taille n. Dans ce cas, vous vous concentrez sur le codomain de f(n) pour certains connus n. Vous visualisez des réponses à des questions sur la durée de l'opération ou la quantité de mémoire consommée par cette opération.
Si vous avez tendance à visualiser n comme un paramètre ayant une valeur quelconque, alors O(log n) est n fois plus évolutif. O(log n) peut compléter n fois autant de tâches de taille n. Dans ce cas, vous êtes concentré sur le domaine de f(n). Vous visualisez les réponses aux questions sur la taille de n ou sur le nombre d'instances de f(n) que vous pouvez exécuter en parallèle.
Aucune perspective n'est meilleure que l'autre. Le premier peut être utilisé pour comparer des approches pour résoudre un problème spécifique. Ce dernier peut être utilisé pour comparer les limites pratiques des approches données.
+1 bel exemple. – tster