From 47e2da7929c9fad9a97c2a6ceea76f00e4a25321 Mon Sep 17 00:00:00 2001
From: Pixel <>
Date: Tue, 17 Apr 2001 22:29:10 +0000
Subject: Pouet (doc)

---
 doc/temps.tex | 26 ++++++++++++++++++++++++++
 1 file changed, 26 insertions(+)
 create mode 100644 doc/temps.tex

(limited to 'doc/temps.tex')

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.
-- 
cgit v1.2.3

