Durée de la boucle for

En parcourant les exemples et les explications de la durée d'exécution des boucles imbriquées sur http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L03-BigOh.htm#Counting, le deuxième exemple ne me semble pas correct.Durée de la boucle for

exemple 1

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

a un sens tout de suite. L'extérieur pour la boucle est O (n). Inner for Loop est également O (n). Multipliez-les ensemble, O(n) * O(n) = O(n*n) = O(n^2).

Deuxième exemple. intérieur de la boucle ne commence pas par 0.

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

le temps de marche de la boucle interne sera (1 + 2 + … + n) = n*(n+1)/2 = O(n^2) Comme dans le premier exemple, la boucle externe fonctionne à O (n). Par conséquent, la durée totale est O(n) * O(n^2) = O(n^3). J'ai raison, ou il me manque quelque chose? Merci!

Source

2011-09-19 newprint

Vous ajoutez la totale temps de fonctionnement de la boucle interne -. Pas le temps d'exécution par itération de la boucle externe. Le temps d'exécution de la boucle interne par itération externe est toujours O (n), ce qui conduit à un résultat global de O (n).

Pour d'autres termes - si vous comprenez le premier exemple, et le second exemple ne moins travail que le premier exemple, comment pourrait-il avoir plus complexité?

Source

2011-09-19 16:05:23

Je pense que j'ai compris où j'avais tort. En effet (1 + 2 + ... + n) = n * (n + 1)/2 = O (n^2) Tout d'abord, la boucle interne dépend de la boucle externe, et vous ne pouvez pas simplement multiplier les complexités comme nous fait dans les exemples précédents. Nous devons compter le nombre d'exécutions de la boucle interne pour toutes les n exécutions de la boucle externe. Par conséquent, nous obtenons des séries faites de n termes. Merci pour votre aide! – newprint

(1 + 2 + … + n) = n*(n+1)/2 = O(n^2) est le total temps pour le programme. Vous n'avez pas besoin de le multiplier par O(n) pour la boucle externe; vous avez déjà pris en compte la boucle externe.

[Note: techniquement, il est correct de dire que l'algorithme est O(n^3). Il est juste un peu trompeur]

Source

2011-09-19 16:05:08

Le temps d'exécution de la boucle interne est d'environ n/2 en moyenne, donc c'est toujours O (n), le même que dans le premier exemple.

Source

2011-09-19 16:13:29

Réponse aux deux premières réponses ci-dessus. Je ne vois pas comment le (1 + 2 + … + n) = n*(n+1)/2 = O(n^2) sera la totale durée

Say, n = 3

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

Durée totale de la boucle interne est 1times + 2FOIS + 3fois

Alors, où boucle extérieure entre en jeu? Il s'exécute O (n) fois aussi (comme il l'a fait dans le premier exemple)

Source

2011-09-19 16:31:50 newprint

Lire le message avec la réponse acceptée pour voir où j'ai fait une erreur logique. – newprint

Durée de la boucle for

Répondre

Questions connexes