\chapter{Analyse de temps} \paragraph{} L'analyse de temps n'est pas tr�s difficile. En effet les diff�rents temps sont d�j� calcul�s pour ce qui est des tas Binomiaux, des tas de Fibonacci et des tas binaires. Nous pr�senterons aussi les temps pour les files de priorit�s. Voici donc les diff�rents temps n�cessaires pour les op�rations de bases pour tous les algorithmes: \paragraph{} \begin{center} \begin{tabular}{lcccc} Proc�dure & Tas binaire & Tas binomial & Tas de Fibonacci & Liste cha�n�e tri�e\\ \hline\\ \textsc{Cr�er-Tas} & $\Theta(1)$ & $\Theta(1)$ & $\Theta(1)$ & $\Theta(1)$\\ \textsc{Ins�rer} & $\Theta(\lg n)$ & $O(\lg n)$ & $\Theta(1)$ & $O(n)$\\ \textsc{Minimum} & $\Theta(1)$ & $O(\lg n)$ & $\Theta(1)$ & $\Theta(1)$\\ \textsc{Extraire-Min} & $\Theta(\lg n)$ & $\Theta(\lg n)$ & $O(\lg n)$ & $\Theta(1)$\\ \textsc{Union} & $\Theta(n)$ & $O(\lg n)$ & $\Theta(1)$ & $O(n)$\\ \textsc{Diminuer-Cl�} & $\Theta(\lg n)$ & $\Theta(\lg n)$ & $\Theta(1)$ & $O(n)$\\ \textsc{Supprimer} & $\Theta(\lg n)$ & $\Theta(\lg n)$ & $O(\lg n)$ & $\Theta(1)$\\ \end{tabular} \end{center} \paragraph{} Les temps de la liste cha�n�e tri�e sont simples � analyser et � expliquer. La liste �tant tri�e et doublement cha�n�e, les op�rations MINIMUM, EXTRAIRE-MIN, et SUPPRIMER sont directes, donc en $\Theta(1)$. Ensuite, l'insertion doit trouver le bon emplacement, donc parcourir au pire toute la liste cha�n�e afin d'effectuer l'insertion. C'est pourquoi l'op�ration UNION est en $O(n)$. De m�me, l'op�ration DIMINUER-CLE va effectuer l'op�ration inverser, et d�placer l'�l�ment vers la gauche jusqu'� trouver sa nouvelle place, donc au pire va parcourir toute la liste. Ce qui nous fait des op�rations en $O(n)$. Enfin, l'op�ration UNION est l'impl�mentation de l'algorithme FUSIONNER du tri fusion. Nous avons donc un temps en $O(n)$ aussi.