Dans le livre Algorithmes de Thomas H.Cormen, j'ai lu quelque chose qui me pose problème, j'aimerais donc que vous m'éclairiez si possible.
Il s'agit du calcul du temps d'exécution de l'algorithme de Tri-Selection dont le pseudo code proposé dans le livre est le suivant :
Procédure TRI-SELECTION(A, n)
Entrées :
A : un tableau
n : le nombre d'éléments du tableau A à tirer
Résultat : Les éléments du tableau A à trier.
1. Pour i = 1 à n-1 :
A. Fixer minimum à i
B. Pour j = i +1 à n :
i. Si A[j] < A[minimum], alors fixer minimum à j
C. Echanger A[i] et A[minimum]
Premièrement l'auteur explique que le temps d'exécution est 𝚯(n^2) en expliquant que l'exécution de la boucle interne est une suite arithmétique égale à (n^2 - n)/2
Ensuite il continue par ces propos qui me posent problème :
"Il existe une autre manière de constater que le temps d'exécution est 𝚯(n^2), sans passer par la suite arithmétique. Nous allons montrer séparément que le temps d'exécution est à la fois O(n^2) et Ω(n^2); en réunissant les bornes asymptotiques supérieure et inférieure, nous obtenons 𝚯(n^2)."
Jusqu'ici tout vas bien. J'ai bien compris la démarche, mais c'est après que les choses se corsent (du moins pour moi) :
"Pour déterminer que le temps d'exécution est O(n^2), observons que chaque itération de la boucle externe exécute la boucle interne au moins n-1 fois"
La je sèche, pour moi chaque itération de la boucle externe exécute la boucle interne au moins UNE FOIS et non pas n-1 comme l'auteur précise. Donc je conclus que ce qu'il voulais dire c'est que chaque itération de la boucle externe exécute la boucle interne au PLUS n-1 fois. Mais dans tout les cas je ne comprend pas son résonnement puisque quoiqu'il arrive les itérations de boucle sont effectuées. Enfin bref, la je ne comprend pas ce que l'auteur essaye de nous faire comprendre.
Il continue ensuite en disant :
"Cela donne O(n) car chaque itération de la boucle interne se fait un un temps constant. Puisque la boucle externe itère n-1 fois, c'est à dire également O(n), le temps total passé dans la boucle interne est O(n) fois O(n), c'est à dire O(n^2).
La suite est encore pire à comprendre (du moins pour moi):
"Pour déterminer que le temps d'exécution est Ω(n^2), observons que dans chacune des n/2 premières itérations de la boucle externe, la boucle interne est exécutée au moins n/2 fois, pour un total d'au moins n/2 multiplié par n/2, c'est à dire n^2/4 fois. Puisque chaque itération de la boucle interne se fait en un temps constant, nous voyons que le temps d'exécution est au moins une constate multiplié par n^2/4, ou Ω(n^2)"
Je n'ai absolument rien compris à cette partie, je ne comprend pas la démarche adoptée par l'auteur pour calculer le temps d'exécution dans le cas le plus favorable, pourquoi prend t-il seulement les n/2 premières itérations de la boucle externe alors qu'elles sont toutes effectuées et ce dans tout les cas.
Je vous remercie d'avance d'avoir pris le temps de lire ce sujet (assez long je le conçois) ainsi que des précisions que vous apporteraient.
[...] "Pour déterminer que le temps d'exécution est O(n^2), observons que chaque itération de la boucle externe exécute la boucle interne au moins n-1 fois"
La je sèche, pour moi chaque itération de la boucle externe exécute la boucle interne au moins UNE FOIS et non pas n-1 comme l'auteur précise. Donc je conclus que ce qu'il voulais dire c'est que chaque itération de la boucle externe exécute la boucle interne au PLUS n-1 fois. Mais dans tout les cas je ne comprend pas son résonnement puisque quoiqu'il arrive les itérations de boucle sont effectuées. Enfin bref, la je ne comprend pas ce que l'auteur essaye de nous faire comprendre.
[...]
La boucle interne s'exécute exactement n-i fois, donc au moins n-i. Un typo sans doute entre 1 et i …
AMB1992 a écrit:
[...]
La suite est encore pire à comprendre (du moins pour moi):
"Pour déterminer que le temps d'exécution est Ω(n^2), observons que dans chacune des n/2 premières itérations de la boucle externe, la boucle interne est exécutée au moins n/2 fois, pour un total d'au moins n/2 multiplié par n/2, c'est à dire n^2/4 fois. Puisque chaque itération de la boucle interne se fait en un temps constant, nous voyons que le temps d'exécution est au moins une constate multiplié par n^2/4, ou Ω(n^2)"
Je n'ai absolument rien compris à cette partie, je ne comprend pas la démarche adoptée par l'auteur pour calculer le temps d'exécution dans le cas le plus favorable, pourquoi prend t-il seulement les n/2 premières itérations de la boucle externe alors qu'elles sont toutes effectuées et ce dans tout les cas.
Il cherche à avoir une boucle interne qui tourne au moins n/2 fois. Pour cela on doit avoir au moins i=n/2. Donc si i est plus petit que n/2 alors tu es certain que la boucle interne effectue au moins n/2 tours. Donc en gros pour le n/2 premiers éléments, la boucle interne fait au moins n/2 tours ⇒ l'algo est en Ω(n²) car le reste des boucle ne peut être qu'inférieur à ça (pour les n/2 éléments suivant, la boucle interne fait moins que n/2 tours).
Calcul de complexité algorithmique
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.