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.
|
