Faire “si” affectent à la fois l'analyse de la complexité?

Pas. Considérer que le temps de la complexité décrit le temps asymptotiquement - nous absorber moins de temps-complexités dans le supérieur.

O(n²) signifie k × n² + c où il est supposé que les c est si faible que nous ne nous soucions pas.

Ce sont les effets de constantes, un certain montant de frais généraux sur l'ensemble de la chose (c) et une certaine quantité de coût par quelle que soit sa complexité. Un n² algorithme va battre un autre n² algorithme si il a un moindre k, ou si elles sont égales, une baisse de la c. Aussi, O(n2) est la même que O(1) pour suffisamment faibles valeurs de n (et normalement, nous ne de soins, mais la k de chacun pourrait être considérablement différent, et si nous le faisons chaque m fois, puis tout en O(n2m) bat O(m), si n est faible, ce n'est pas ce qui est vraiment contre)..

De toute façon, c'est une volonté délibérée de simplification, parce que k et c peut pas vraiment être constante, aussi bon que constante. Donc, si quelque chose était vraiment O(n² + log(n)), nous préférons l'appeler O(n²), car qui se soucie que peu de log(n) lorsque nous avons un n² inquiéter?

. En regardant votre cas. Nous faisons la boucle externe, n fois. Pour chacun de ceux-ci, nous faisons la boucle interne n-1 fois. Pour chacune de ces boucles internes nous ne la première impression (tout écart dans les coûts n'est pas liée à n en aucune manière, essentiellement constant) et le test. Le test réussit à peu près la moitié du temps, d'où le coût de la deuxième impression que souvent.

De sorte que le coût total est:

cost of setting up everything +
n × cost of looping + 
(n - 1) × cost of loop +
(n × (n - 1)) × cost of print +
(n × (n - 1)) × cost of test +
(n × (n - 1)) / 2 × cost of print.

De l'attribution des valeurs pour les constantes ci-dessus, nous obtenons:

k +
n × a +
(n - 1) × b +
(n × (n - 1)) × c +
(n × (n - 1)) × d +
(n × (n - 1)) / 2 × e.

=

k +
n × a +
(n - 1) × b +
(n × (n - 1)) × (c + d + (e / 2))

Maintenant, depuis c + d + e /2 est elle-même constante, qui peut devenir:

n × a + (n - 1) × b + (n × (n - 1)) × c + k

Ou de commander à nouveau, dans l'ordre de plus haut ordre premier:

(n × (n - 1)) × c + (n - 1) × b + n × a + k

Si n est suffisamment élevé pour nous de donner une merde, alors n est proportionnellement si proche de n - 1 que l'on pourrait aussi bien considérer la même (un autre aspect de la complexité temporelle décrivant les choses à l'infini, c'est comme n approches ∞ et donc la différence entre n2 et (n × (n - 1)) sont proches de 0). Donc:

n² × c + n × b + n × a = n² × c + n × (b + a) + k

De nouveau, b + a est elle-même constante, il est donc équivalente à:

n² × k + n × c + a

Et maintenant nous allons faire ce qui a été mentionné plus tôt que d'absorber la baisse des commandes en temps, qui se soucie de n × c, jamais l'esprit? Si n est suffisamment élevé pour que nous nous occupions à tous, il est tout au sujet de n². À titre de comparaison, on peut simplement considérer la différence de l'ensemble des frais généraux comme le bruit et la traiter comme:

n² × k + c

Ou, en d'autres mots, comme:

O(n²)

Donc, oui, vous étiez bang sur elle pour commencer avec, et si l'instruction n'a pas d'incidence sur la complexité.

Considérant cela, on peut noter qu'il est possible que le temps de la complexité de masquer ce que nous nous soucions vraiment de. Si par exemple, nous avons eu un O(n2) de l'algorithme ont ce type d'analyse a permis de constater un coût de temps de n² × k + n × c étaient k s'élève à 200µs et c s'établit à 15 ans, puis jusqu'à ce que n est plus grand que 750000 c'est en fait le nombre n de bits que les coûts, plutôt que de le par-n2 bits. Au bas n c'est plus proche de ce que nous attendons de O(n) que de O(n2).

La raison le temps de la complexité est utile, est une combinaison d'une si grande disparité étant rares, et que nous nous soucions de temps, et donc sur le temps-de la complexité, de plus lorsque n augmente (vous pouvez masquer certains horrible O(n!) monstruosité dans votre code que vous appeler une fois dans une lune bleue, avec trois éléments et tout simplement pas de soins). Donc, pour amener dans le monde réel des améliorations idéalement nous voulons réduire la complexité du temps, ou, à défaut, réduire le niveau le plus élevé de la constante k (ou en d'autres termes, si vous pouvez commencer à faire des choses n log n fois au lieu de n2 fois, puis les faire, sinon de réduire le coût de cette chose que vous faites n2 fois, plutôt que quelque chose que vous êtes en train de faire n fois).

En d'autres termes, il nous aide à nous concentrer sur ce que normalement mattres.

OriginalL'auteur Jon Hanna

La complexité du temps est le même, vous aurez l'impression Yayyyy N^2 fois.

OriginalL'auteur Per Alexandersson

Réponse courte: le temps d'Exécution est toujours en O(N^2).

Réponse longue: Le coût de la réserve de vérification peut en toute sécurité être "ajouté" le poids de la println opération, le même que si au lieu de faire une println(), vous aviez deux println (). (À propos de l'exemple, l'ours à l'esprit que le coût des opérations d'e/S comme println emportent largement sur simple entier comparaisons.)

Peut-être que vous pourriez dire que la println() coûts des appels "1", et la comparaison est "0.0001 opération", de sorte que le coût total devrait être "(1.0001 * N)^2 opérations au lieu de simplement N^2. Vous avez également de réduire le nombre d'println()'s dans la moitié, de sorte que nous pouvons dire que vous êtes à (1.0001 * N) ^ 2 /2 opérations. C'est toujours en O(N^2), même si que pour une valeur donnée de N vous pouvez avoir réduit de moitié le moteur d'exécution par l'impression que la moitié des entrées.

En général, le coût de la comparaison doit être ajouté au coût des opérations au sein de la branche(es) résultant de la comparaison. Lorsque les deux if() {} else {} sont présents, il peut être plus difficile à mesure de l'exécution. Une tactique ici est d'estimer l'exécution si le plus cher de l'opération se produit chaque fois; ou, si l'exécution d'une seule branche n'est pas facilement trouvable, estimation, comme si les deux les opérations se produisent à chaque itération de boucle. Si ces opérations sont à la fois O(1), l'ordre d'exécution reste en O(N^2) puisque vous êtes mise à l'échelle linéaire.

OriginalL'auteur lyngvi