Comment calculer le pire des cas, l'analyse de cet algorithme?

sum = 0;
for(int i = 0; i < N; i++)
    for(int j = i; j >= 0; j--)
       sum++;

De ce que je comprends, la première ligne est 1, 2ème ligne est (i+1) opérations, 3e ligne est (i-1) opérations, et de la 4ème ligne est n opérations. Est-ce à dire que le temps d'exécution serait 1 + (i+1)(i-1) + n? C'est juste que ces derniers pas qui me confondre.

Vous avez besoin de calculer la complexité par rapport à N, de ne pas les compteurs de boucles.

OriginalL'auteur | 2011-01-29

6

Pour analyser l'algorithme que vous ne voulez pas aller ligne par ligne, en demandant "combien de temps cette ligne en particulier contribuer?" La raison en est que chaque ligne n'a pas d'exécuter le même nombre de fois. Par exemple, le centre le plus intime de la ligne est exécutée tout un tas de fois, par rapport à la première ligne qui est exécuté une seule fois.

Pour analyser un algorithme comme celui-ci, essayez d'identifier une certaine quantité dont la valeur est inférieure à un facteur constant de la durée totale d'utilisation de l'algorithme. Dans ce cas, cette quantité serait probablement "combien de fois la ligne sum++ exécuter?", car si nous savons que cette valeur, nous savons que le temps total consacré par les deux boucles de l'algorithme. Pour comprendre cela, nous allons suivre ce qui se passe avec ces boucles. À la première itération de la boucle externe, i == 0 et donc la boucle intérieure va exécuter exactement une fois (en partant de 0 à 0). Sur la deuxième itération de la boucle externe, i == 1 l'intérieur de la boucle s'exécute exactement deux fois (d'abord avec j == 1, une fois avec j == 0. Plus généralement, sur la k-ième itération de la boucle externe, à l'intérieur d'une boucle k + 1 fois. Cela signifie que le nombre total d'itérations de la boucle de plus bas niveau est donné par
```
1 + 2 + 3 + ... + N
```
Cette quantité peut être montré pour être égale à
```
N (N + 1)      N^2 + N    N^2    N
---------   =  ------- =  --- + ---
    2             2        2     2
```
De ces deux termes, l' N^2 /2 terme est la dominante de la croissance de long terme, et donc, si nous ignorons sa constante facteurs, nous obtenons un temps d'exécution de O(N²).

Ne regarde pas cette réponse est quelque chose que vous devez mémoriser - pensez à toutes les étapes requises pour obtenir la réponse. Nous avons commencé par trouver une certaine quantité de compter, et ensuite, vu la façon dont la quantité a été influencé par l'exécution de la boucle. À partir de cela, nous avons été en mesure de dériver une expression mathématique de cette quantité, qui nous a ensuite simplifié. Enfin, nous avons pris l'expression qui en résulte et déterminé la dominante terme, qui sert de big-O pour l'ensemble de la fonction.

OriginalL'auteur templatetypedef
2

De l'intérieur.
```
sum++
```
C'est une opération unique sur son propre, car il ne se répètent pas.
```
for(int j = i; j >= 0; j--)
```
Cette boucle de i+1 fois. Il y a plusieurs opérations de là, mais vous n'avez probablement pas le moyen de compter le nombre d'instructions asm. Je vais donc supposer, pour cette question, c'est un multiplicateur de i+1. Depuis la boucle de contenu est une seule opération, de la boucle et son bloc d'effectuer i+1 opérations.
```
for(int i = 0; i < N; i++)
```
Cette boucle de N fois. Alors comme avant, c'est un multiple de N. Depuis le bloc effectue i+1 opérations, cette boucle effectue N(N+1)/2 opérations au total. Et c'est votre réponse! Si vous voulez considérer big-O de la complexité, alors cela simplifie à O(N²).

OriginalL'auteur marcog
1

Ce n'est pas additif: la boucle interne se produit une fois pour CHAQUE itération de la boucle externe. Il est donc O(n²).

Par la voie, c'est un bon exemple de pourquoi nous utilisons la notation asymptotique pour ce genre de chose, selon la définition de "l'opération" les détails exacts du comte peut varier assez largement. (Comme, est sum++ une seule opération, ou est-il add sum to 1 giving temp; load temp to sum?) Mais puisque nous savons que tout ce qui peut être caché dans un facteur constant, il va toujours à O(n²).

OriginalL'auteur Charlie Martin
0

Pas; on ne compte pas un nombre spécifique d'opérations pour chaque ligne, puis de les additionner. L'ensemble de la point de des constructions comme "pour" est de rendre possible pour une ligne de code à exécuter plus d'une fois. Vous êtes censé utiliser la réflexion et de la logique de compétences pour comprendre combien de fois la ligne " somme++ de s'exécuter, en fonction de N. remarque: il est exécuté une fois pour chaque fois que la troisième ligne est rencontré.

Combien de fois est la deuxième ligne rencontrés?

Chaque fois que la deuxième ligne est rencontré, la valeur de " i " est défini. Combien de fois est-ce que la troisième ligne exécuter avec la valeur de i? Donc, combien de fois peut-il fonctionner? (Astuce: si je vous donne un autre montant d'argent à plusieurs reprises, comment trouvez-vous le montant total que je vous ai donné?)

Chaque fois que la troisième ligne est rencontré, la quatrième ligne arrive qu'une fois.

La ligne à laquelle se produit le plus souvent? Combien de fois se fait-il, en termes de N?

OriginalL'auteur Karl Knechtel
0

Donc deviner ce qui vous intéresse est la somme++ et combien de temps vous l'exécuter.

La dernière stat de la somme serait de vous donner cette réponse.

Fait ta boucle est juste:

Sigma(n) n va de 1 à N.

Qui égale à: N*(N+1) /2 Cela vous donne en big-o-notation O(N^2)

Aussi à côté du nom de votre question, il n'y a pas de pire des cas, à vous de l'algorithme.
Ou on pourrait dire que dans le pire des cas, lorsque N tend vers l'infini.

OriginalL'auteur mathk
0

À l'aide de notation Sigma pour représenter vos boucles:

OriginalL'auteur Mohamed Ennahdi El Idrissi

Vous devez vous connecter pour publier un commentaire.