Informatique algorithme complexité - Confusion

Question

Je l'extrait de code de code suivant:

sum = 0;
for (i = 0; i < n; i++)
    for (j = 0; j < i; j++)
        sum++;

La complexité serait O(n^2), mais si je veux creuser un peu plus pour la complexité de la boucle interne alors il est (n (n-1))/2 ou (n-1)!?

Answer 1

Oui, O (n ^ 2), mais en fait 0 + 1 + ... + n-1 = n (n-1) / 2 = O (n ^ 2), certainement pas (n-1)!

Answer 2

time = n*(n-1)/2
     = (n*n - n)/2

Depuis la notation grand-O est une limite supérieure, le terme d'ordre inférieur (-n) et le facteur constant (1/2) sont tous deux enlevés (car ils ne sont pas significatifs pour représenter la limite supérieure du temps) pour donner la notation grand-O, O(n*n) mieux connu sous le nom O(n^2).

Answer 3

Vous pourriez avoir un algorithme qui fonctionne en temps

22222222222222 + 4444444444444*n + 9999999999999999999999999*n^2 steps

Et il serait encore O (n ^ 2).

Il est un problème ouvert pour trouver une meilleure description pour le temps que l'exécution algorithme O.

Answer 4

Constantes sont sans incidence sur la notation grand-O est concerné.

Answer 5

Qu'est-ce que vous avez calculé (n(n-1)/2) est le nombre exact d'itérations pour le code. Lorsqu'on lui a demandé de la complexité du temps en termes si grand O, vous donner une estimation qui est juste assez grand pour exprimer le temps.

En d'autres termes, vous devez trouver THE SMALLEST power de n tel que pour certains k (k>0), k * n^power sera plus grand que le nombre exact d'itérations. Dans votre cas, k arrive à 1 et power arrive à 2. Ensuite O(n^power) est la complexité de votre temps.

Answer 6

Tout d'abord, (n-1)! signifie (n-1)(n-2)...(2)(1). Ceci est clairement pas ce que vous voulez ici.

Si vous comptez le nombre réel d'itérations il est 0 + 1 + 2 + ... + (n-2) + (n-1). Notez qu'il existe des termes n dans la somme, et que nous pouvons les apparier de manière telle que la valeur moyenne de chaque paire est (n-1)/2. (Paire le plus haut et le plus bas, le deuxième plus haut et plus bas seconde, etc.) Si n est impair, vous aurez une gauche qui ne peut plus être couplé, mais sa valeur pratique est également (n-1)/2. Ainsi, vous avez n termes et la moyenne de tous les termes est (n-1)/2, de sorte que la somme totale est n(n-1)/2.

Maintenant, pour la notation grand O ne combien d'itérations nous avons pas d'importance exactement - nous voulons juste connaître la limite quand n est très grande. Notez que notre nombre d'itérations peut être écrit comme (1/2)n^2 - (1/2)n. Pour les très grands n, le terme de n^2 est beaucoup, beaucoup plus grand que le terme n, donc nous laissons tomber le terme n. Cela nous laisse juste avec (1/2)n^2, mais une autre règle de notation grand O est que nous ne se soucient pas du facteur constant, donc nous écrivons juste que c'est O (n ^ 2).