Bonjour à tous.
J'ai 3 algos dont j'aimerais déterminer la complexité donc je viens vers vous pour y arriver.

Algo 1 :

Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
 
t = 0
i = 0
while i × i < N do
t = t + i
i = i + 1
return t
Selon moi l'algo optimise au maximum le nombre d'itérations à effectuer donc du coup je déduit que la complexité est O(logN) mais je ne suis pas sûr de moi.

Algo 2 :

Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
 
t = 0
i = 1
while log<sub>2</sub>i < N do
t = t + i
i = i + 1
return t
Là comme log2i = 0 la condition est toujours vérifiée donc boucle infinie ce qui m'amène à supposer que la complexité est O(infini) à moins que N soit négatif ce qui ne peut jamais être le cas en algorithmique.Là aussi je ne suis pas sûr de moi.

Algo 3 :

Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
 
t = 0
for i allant de 1 `a n do
j = 1
while log<sub>2</sub>j < i do
t = t + j
j = j + 1
return t
Dans ce 3ème algo je vois 2 boucles imbriquées et il me semble que la 2ème est infinie mais je n'arrive pas à me faire une idée de sa complexité.

D'avance merci pour vos éclaircissement.