Discussion :

[Ja Rasta]

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 log₂i = 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.

[picodev]

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.

Bonjour,
Il faut bien indenter même quand c'est du pseudo-code, je vais partir du principe que tu cherches la compléxité temporelle, que l'algo est :

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

et aussi que toutes les opérations (assignation, opérations arithmétiques, etc …) se font en temps constant.
La complexité d'une ligne est la complexité de l'opération effectuée sur cette ligne.
La complexité d'une boucle est la complexité de l'intérieur de la boucle multiplié par le nombre de tours de boucle.
Les lignes 1,2 et 6 sont en temps constant, tout comme les lignes 4 et 5. Mais les lignes 4 et 5 sont dans une boucle qui fait √N tours (à prouver évidemment mais bon … on incrémente i de 1 jusqu'à atteindre √N).
La complexité temporelle de cet algo (sous les hypothèses que j'ai faites) est donc en O(√N), elle est même en 𝛩(√N).

Algo 2 :
...

Algo 3 :
...

D'avance merci pour vos éclaircissement.

Je te laisse refaire les deux autres

[Ja Rasta]

Salut,

La complexité temporelle de cet algo (sous les hypothèses que j'ai faites) est donc en O(√N), elle est même en 𝛩(√N).

S'il vous plaît pouvez-vous m'expliquer la différence entre O(√N) et 𝛩(√N)?et si possible avec un exemple à l'appui puisque j'ai des problèmes avec ces annotations

(j'ai remplacé le symbole inférieur < par inférieur ou égal <= car sinon j'ai une erreur dans mes formules latex, mais il faut lire des <).

Est-ce que ça veut dire que j'ai bien raison avec le signe < nous sommes à une exécution sans fin et que la complexité peut bien être O(infini)?

Merci d'avance!!!

[picodev]

S'il vous plaît pouvez-vous m'expliquer la différence entre O(√N) et 𝛩(√N)?et si possible avec un exemple à l'appui puisque j'ai des problèmes avec ces annotations

Voit ça comme un encadrement :
O → signifie que la complexité est bornée «au-dessus» = au pire ça ne pouura pas être plus
𝛩 → signifie que la complexité est bornée «au-dessus» et «en-dessous» = c'est exactement
𝛺 →signifie que la complexité est bornée «en-dessous» = au mieux ça ne pourra pas être moins

Est-ce que ça veut dire que j'ai bien raison avec le signe < nous sommes à une exécution sans fin et que la complexité peut bien être O(infini)?

Merci d'avance!!!

O(∞) ça n'existe pas. Tes algos terminent, essaye de les dérouler à la main pour visualiser combien d'opérations tu effectues.
Les deux autres algo sont en O(2ⁿ) pour te donner une indication.

[Ja Rasta]

Merci beaucoup.ça m'a vraiment aidé.

[François DORIN]

Bonjour,

Pour l'algo 1, je dirais que la complexité est en , puisque la condition de boucle est i²<n et que i est incrémenté de 1 à chaque fois.

Pour l'algo 2, je dirais que la complexité est en , puisque la condition peut s'écrire et que i est toujours incrémenté de 1. (j'ai remplacé le symbole inférieur < par inférieur ou égal <= car sinon j'ai une erreur dans mes formules latex, mais il faut lire des <).

Pour l'algo 3, au pire la complexité est en , mais il est sans doute possible de raffiner un peu...