summaryrefslogtreecommitdiff
path: root/doc/temps.tex
blob: 87635538e65e620bf9c457621c47ca1252f36384 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
\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.