Bonjour le prof nous a donné une correction sur un exercice de complexité algorithmique mais je n'ai pas tout compris. Pouvez -vous m'aider ?
Voici l'exercice :
DEBUT :
-i <-- 1
- TQ i <= n FAIRE :
----j <-- 2
----TQ j<= (n^0.5) FAIRE :
--------J <-- j+1
-----FTQ
-----i<-- 1
-FTQ
FIN
Correction :
Boucle intérieur :
- La boucle ne dépend que de la variable j
- j est initialisé a 2 avant la boucle
-Elle est modifiés a l'instruction 7 (j<-- j+1)
- Les valeurs prisent par j sont donc celles de la suite : j0= 2; jr+1= jr +1 autrement dit jr=2+r
- La condition d’arrêt de la boucle est satisfaite quand j>(n^0.5)
c'est à dire 2+r > (n^0.5) autrement dit r=(n^0.5)-1 // J'ai pas compris comment on est passé de 2+r>(n^0.5) à r=(n^0.5)-1
- Toute les opérations de la boucle sont en Θ(1) on en déduit donc que : // J'ai pas compris pourquoi elles sont en Θ(1), comment on le sait ?
c(n)= Θ(1) *((n^0.5)-1)=Θ((n^0.5)-1)=Θ((n^0.5)) // Ici je n'ai absolument rien compris au calcule
Boucle principal :
- La boucle ne dépend que de la variable i
- j est initialisé a 1 avant la boucle
-Elle est modifiés a l'instruction 9 (i<-- i+1)
- La condition d’arrêt de la boucle est satisfaite quand i=n+1
- La complexité de la boucle principal est Θ(1)+Θ(n^0.5)= Θ(n^0.5) // Ici idem que en haut j'ai pas compris le calcule
Pour la complexité total = Θ(n*(n^0.5)) // Il faut additionner les complexité des 2 boucles ?
Je vous remercie pour votre aide !!
-----