<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\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 &amp; Tas binaire &amp; Tas binomial &amp; Tas de Fibonacci &amp; Liste cha�n�e tri�e\\
\hline\\
\textsc{Cr�er-Tas} &amp; $\Theta(1)$ &amp; $\Theta(1)$ &amp; $\Theta(1)$ &amp; $\Theta(1)$\\
\textsc{Ins�rer} &amp; $\Theta(\lg n)$ &amp; $O(\lg n)$ &amp; $\Theta(1)$ &amp; $O(n)$\\
\textsc{Minimum} &amp; $\Theta(1)$ &amp; $O(\lg n)$ &amp; $\Theta(1)$ &amp; $\Theta(1)$\\
\textsc{Extraire-Min} &amp; $\Theta(\lg n)$ &amp; $\Theta(\lg n)$ &amp; $O(\lg n)$ &amp; $\Theta(1)$\\
\textsc{Union} &amp; $\Theta(n)$ &amp; $O(\lg n)$ &amp; $\Theta(1)$ &amp; $O(n)$\\
\textsc{Diminuer-Cl�} &amp; $\Theta(\lg n)$ &amp; $\Theta(\lg n)$ &amp; $\Theta(1)$ &amp; $O(n)$\\
\textsc{Supprimer} &amp; $\Theta(\lg n)$ &amp; $\Theta(\lg n)$ &amp; $O(\lg n)$ &amp; $\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.
</pre></body></html>