Complexité d'un algorithme
Bonjour à tous.
J'ai 3 algos dont j'aimerais déterminer la complexité donc je viens vers vous pour y arriver.
Algo 1 :
Code:
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:
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:
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.
