[complexité] d'un algorithme

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:

---

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:

---

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

Citation:

---

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.

Citation:

---

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;))

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)²).

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

ouai je me suis tromper en écrivant.

Merci pour le coup de pouce.

Tchao