Quelle est la bonne notation O pour un algorithme qui s'exécute en triangular? Voici un exemple:Grande notation O pour les nombres triangulaires?
func(x):
for i in 0..x
for j in 0..i
do_something(i, j)
Mon premier instinct est O(n²), mais je ne suis pas tout à fait sûr.
Oui, N * (N + 1)/2, lorsque vous supprimez les constantes et les termes d'ordre inférieur, vous laisse avec N-carré.
Ouais, O(n^2) est correcte definitly. Si je me souviens bien, O est de toute façon toujours une limite supérieure, donc O(n^3) devrait également être correct, comme O(n^n) ou autre. Cependant O(n^2) semble être le plus serré qui est facilement déductible.
Si vous pensez mathématiquement, la zone du triangle vous calcul est ((n+1)^2)/2. C'est donc le temps de calcul: O (((n + 1)^2)/2)
Le temps de calcul augmente de N * (N + 1)/2 pour ce code. C'est essentiellement O (N^2).
lorsque l'entrée augmente de n à 2n alors le temps de fonctionnement de votre algorithme va augmenter de t à 4t
temps de fonctionnement ainsi est proportionnelle au carré de la taille d'entrée
si l'algorithme est O (n^2)
O (! n) gère des cas pour un calcul factoriel (temps triangulaire).
Il peut aussi être représenté comme O (n^2) pour moi cela semble être un peu trompeur car le montant en cours d'exécution sera toujours moitié moins que O (n^2) effectuerait.
Par définition, 'O (0.5 * n^2) == O (n^2)' (une égalité qui vaut pour tout facteur constant non nul, en fait), donc d'un point de vue strictement théorique, cela n'est pas trompeur. :-) – Gijs
-1. Un [Factoriel] (http://en.wikipedia.org/wiki/Factorial) n'est pas le même qu'un [nombre triangulaire] (http://en.wikipedia.org/wiki/Triangular_number). – gilly3
Vous avez raison ... O ((n + 1) choisissez 2) = O (n^2) par définition. – Protostome