Discussion :

[charlix]

Bonjour,

Je suis totalement nouveau pour ce qui s'agit de la complexité d'un algo, donc j'aurais besoin d'un petit coup de pouce.
On me demande la complexité de deux algos. Bon ils sont pas très lourd mais bon, j'aimerais bien comprendre.
Il me faut la complexité en comptabilisant que les additions.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
Fonction somme(n) -> entier
debut
som <- 0
pour i variant de 1 à n faire
som <- som + i
fpour
Resultat_fct_somme <- som
Fin

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
Procédure tata(n, s)
Début
s . 0
pour i variant de 1 à n faire
m <-- m + i
finpour
pour i variant de 1 à m*m faire
s . s+i
fpour
fin

Pour le premier algo, si je comprend bien, la complexité est de n car il y a une boucle faisant varier i de 1 à n.

Mais pour le deuxième, j'ai un peu de mal à saisir.
Quelqu'un pourait-il éclairer un illuminé ?

Merci tchao

[PRomu@ld]

Pour le premier algo, si je comprend bien, la complexité est de n car il y a une boucle faisant varier i de 1 à n.

LA complexité est en Theta(n), et pas de n. La complexité est un comportement, si tu dis de n, ça n'a pas énormément de sens et ça peut te perdre pour la suite.

Mais pour le deuxième, j'ai un peu de mal à saisir.

Le gros problème avec ton deuxième algo, c'est qu'il n'est pas correct. Si tu suppose que m est initialisé à 0 au début de ton algorithme. A la fin de la boucle for, m vaut la somme des entiers de 1 à n, pour le reste du programme, le principe est comme ton premier algo, tu pourras donc trouver la complexité facilement (je ne vais pas te la donner directement)

[charlix]

Si je comprend bien alors, on a dans la premiere boucle de l'algo n additions et dans la deuxieme boucle on en a m². Donc cela voudrais dire que l'on a une complexité de theta (n+m²) mais vu que m est la somme des entiers de 1 à n alors on a une complexité de theta (n+(n(n-1)/2)²).

[PRomu@ld]

la somme des éléments de 1 à n, c'est n(n+1)/2, mais sinon, c'est ça.

[charlix]

ouai je me suis tromper en écrivant.

Merci pour le coup de pouce.

Tchao