1 files changed, 26 insertions, 0 deletions
diff --git a/doc/temps.tex b/doc/temps.tex
new file mode 100644
index 0000000..8763553
--- /dev/null
+++ b/doc/temps.tex
@@ -0,0 +1,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.