Compte tenu du code suivant, quelle est la complexité de 3. et comment puis-je représenter des algorithmes simples avec les complexités suivantes? O (N ° N ° + N)
O (N ° + 2n)
O (logn)
O (nlogn)
5 Réponses :
3 est O (n * m), ou O (n ^ 2) si les deux collections ont la même taille.
o (n ^ 2 + n) est inutile car n est inférieur à N ^ 2. Juste écrire o (n ^ 2).
La plus décente Tri de comparaison algorithmes exécutez à O (n * journal (n)). Si vous ne connaissez pas, regardez sur Wikipedia.
a Recherche binaire est O (journal (n)).
Merci. Donné O (n * m) = O (n ^ 2) pour des ensembles de la même taille, si un ensemble est la moitié de l'autre quelle est la complexité résultante?
Pour clarifier, je dirais que l'ordre d'algorithme N-carré si les deux collections devraient être proportionnelles de taille. Sinon, le O (n * m) est plus approprié.
@Ben Aston: Vous pouvez ignorer les coefficients de la notation O (n). Si m = n / 2 puis O (n * m) = O (n ^ 2/2) = O (n ^ 2).
John, tu es tort. Si les tailles sont N et N / 2 La complexité est O (n ^ 2).
L'extérieur Comment devrais-je représenter des algorithmes simples avec les complexités suivantes?
C'est la même chose que O (n ^ 2). Quelque chose qui prend du temps de (n ^ 2) boit un toast avec toutes les autres personnes lors d'une fête, en supposant qu'il y a toujours exactement deux personnes dans un toast, et une seule personne fait le grillage à la fois.
même que ci-dessus; le terme O (n ^ 2) domine. Un autre exemple d'effort O (N ^ 2) est en train de planter des arbres dans un jardin carré de longueur Un exemple de ceci trouverait un mot dans un dictionnaire en choisissant à plusieurs reprises le point médian de la région des pages dont vous avez besoin pour rechercher ensuite. (En d'autres termes, une recherche binaire.)
Utilisez l'algorithme ci-dessus, mais vous devez maintenant trouver chaque mot dans le dictionnaire. foreach est exécuté n = | C1 | Times (où | x | est la taille de C1 ), tandis que l'intérieur foreach est exécuté m = | c2 | fois. C'est o (n * m) fois au total.
n , en supposant qu'il faut du temps constant pour planter chaque arbre et qu'une fois que vous planterez un arbre, d'autres arbres sont exclus. de ses environs.
C'est une explication fantastique. Bien qu'il s'agisse d'une doublure, votre explication de O (n log n) a vraiment cliqué.
La complexité de 3 est O (m * n).
Il n'y a pas de complexité O (n 2 + n) ou O (n 2 + 2n). C'est juste O (n 2 ). C'est parce que n est O (n 2 ).
Exemple de O (journal (n)) est une recherche binaire.
Exemple de O (n * journal (n)) est la fusion du tri.
De plus, depuis par définition BIG-O est le scénario pire cas si vous avez quelque chose qui est O (n ^ 2), alors O (n ^ 2 + n) n'est pas différent à long terme B / C THE N ^ 2 l'emporte sur.
Il n'y a pas de O (N² + N) ou O (N ^ 2 + 2N). En laissant de côté la plupart des fondements mathématiques de la complexité algorithmique, vous avez au moins besoin de savoir que c'est «aymptotique». Comme N approche l'infini, la valeur de N ^ 2 + N est dominée par le terme N ^ 2, de sorte que la complexité asymptotique de N ^ 2 + N.
La complexité de 3 3 est O (i * j), où i et J sont la taille des entrées en C1 et C2.
vérité être dit O (n² + n) & o (n² + 2n) sont les mêmes.