\input{../.headers/cours.tex}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\newcommand{\ceil}[1]{\left\lceil #1 \right\rceil}

\baselineskip15pt

\begin{center}
\shadowbox{\LARGE \bf \textsc{\supline Calculs de complexit\'e\subline}}\\
\end{center}

\smallskip

\section{D\'efinitions et premi\`eres propri\'et\'es}

\smallskip

\subsection{Complexit\'e en temps}

\smallskip

\dfn
$\bullet$ La complexit\'e {\bf en temps} d'un algorithme {\bf dans le pire des cas} est le plus grand nombre possible d'op\'erations \'el\'ementaires effectu\'ees pour obtenir le r\'esultat en fonction de la taille de la donn\'ee entr\'ee.\subline\\
$\bullet$ La complexit\'e {\bf en temps} d'un algorithme {\bf dans le meilleur des cas} est le plus petit nombre possible d'op\'erations \'el\'ementaires effectu\'ees pour obtenir le r\'esultat en fonction de la taille de la donn\'ee entr\'ee.\subline\\
$\bullet$ La complexit\'e {\bf en temps} d'un algorithme {\bf en moyenne} est le nombre {\bf moyen} d'op\'erations \'el\'ementaires effectu\'ees pour obtenir le r\'esultat en fonction de la taille de la donn\'ee entr\'ee (on consid\`ere \'equiprobables toutes les donn\'ees de taille $n$).\subline\\
$\bullet$ Les notions d'{\it op\'eration \'el\'ementaire} et de {\it taille des donn\'ees} d\'epend du contexte o\`u elle doit \^etre pr\'ecis\'ee. On dit qu'on a diff\'erents {\it mod\`eles de calcul}.\subline
\nfd

Sauf mention explicite du contraire, on s'int\'eresse uniquement \`a la complexit\'e dans le pire des cas.

\bigskip

\rmq\ \\[-0.7cm]
Le nombre de chiffres en base $2$ de l'entier $n$ est $\floor{\log_2(n)}$.
\qmr

\bigskip

\rmq\ \\[-0.7cm]
On peut donner une d\'efinition plus formelle et totalement explicite, mais elle n'est ni praticable ni utile.
\qmr

\bigskip

\subsection{Complexit\'e en espace}

\smallskip

\dfn
$\bullet$ La complexit\'e {\bf en espace} d'un algorithme {\bf dans le pire des cas} est la plus grande taille possible de la m\'emoire utilis\'ee pour obtenir le r\'esultat en fonction de la taille de la donn\'ee entr\'ee.\subline\\
$\bullet$ La complexit\'e {\bf en espace} d'un algorithme {\bf dans le meilleur des cas} est la plus petite taille possible de la m\'emoire utilis\'ee pour obtenir le r\'esultat en fonction de la taille de la donn\'ee entr\'ee.\subline\\
$\bullet$ La complexit\'e {\bf en espace} d'un algorithme {\bf en moyenne} est le taille {\bf moyenne} de la m\'emoire utilis\'ee pour obtenir le r\'esultat en fonction de la taille de la donn\'ee entr\'ee (on consid\`ere \'equiprobables toutes les donn\'ees de taille $n$).\subline\\
$\bullet$ Le sens du mot "taille" est pr\'ecis\'e par le contexte.
\nfd

Sauf mention explicite du contraire, on s'int\'eresse uniquement \`a la complexit\'e dans le pire des cas.

\bigskip

\rmq\ \\[-0.7cm] Si le r\'esultat est de taille $f(n)$, la complexit\'e en espace est {\bf au moins} de $f(n)$, mais elle peut \^etre plus importante.
\qmr

\bigskip

\exx\ \\
Pour calcul it\'eratif des binomiaux vu en TP, le r\'esultat est un entier.\\
On consid\`ere ici les entiers comme \'etant de taille $O(1)$~; la complexit\'e en espace est $O(nk)$.
\xxe

\subsection{Expression d'une complexit\'e}

\smallskip

\dfn[Rappel]
$\bullet$ On dit que $\big(c_n\big)_n$ est domin\'ee par $\big(u_n\big)_n$ et on note $c_n=O(u_n)$ lorsqu'il existe une constante $K>0$ telle que $c_n \leq K u_n$ APCR.\subline\\
$\bullet$ On dit que $\big(c_n\big)_n$ est de m\^eme ordre de grandeur que $\big(u_n\big)_n$ et on note $c_n=\Theta(u_n)$ lorsqu'il existe des constantes $ k_1, k_2 >0$ telles que $k_1 u_n \leq c_n \leq k_2 u_n$ APCR.
\nfd

\smallskip

En pratique, on essaie d'exprimer une complexit\'e $c_n$ par son ordre de grandeur~: $c_n=\Theta(\cdots)$.\\[0.25cm]
Lorsque ce n'est pas possible, on se contente d'une domination~: $c_n=O(\cdots)$.

\bigskip

\rmq\ \\[-1.22cm]
\phantom{\textbf{Remarque 4~:}} $\mathrm{log}_b(n) = \Theta(\lg(n))$.\\
\qmr


\subsection{Complexit\'es usuelles}

\medskip

On s'int\'eressera principalement aux algorithmes dont la complexit\'e $c_n$ est~:\megasubline
\begin{enumerate}
	\item Born\'ee~: $c_n = O(1)$.
	\item Logarithmique~: $c_n = \Theta(\lg(n))$.
	\item Lin\'eaire~: $c_n = \Theta(n)$.
	\item Quasi-lin\'eaire~: $c_n = \Theta(n \lg n)$.
	\item Quadratique~: $c_n = \Theta(n^2)$.
	\item Polynomiale~: $c_n = \Theta(n^k)$.
	\item Exponentielle~: $\lambda^n = O(c_n), \lambda > 1$.
\end{enumerate}

\bigskip

\section{Exemples}

\smallskip

\subsection{Somme et produit de deux entiers}

\exx D\'eterminons le nombre $c_{a,b}$ d'{\bf additions bit-\`a-bit} dans le calcul de $a+b$.
\begin{itemize}
	\item $\overline{43}^{10} = \overline{101011}^{2}$
	\item $\overline{21}^{10} = \overline{010101}^2$
	\hline 
	\item $\overline{64}^{10} = \overline{1000000}^2$
\end{itemize}

On fait $\Theta(1)$ opérations bit à bit pour chaque chiffre, il y a  \[
\begin{cases}
	\lg(a) & \text{chiffres pour $a$} \\
	\lg(b) & \text{chiffres pour $b$} \\
\end{cases}
\] 

On a donc $c_{a, b} = \Theta(\max \{\lg a, \lg b\}) $

\xxe

\exx D\'eterminons le nombre $c_{a,b}$ d'{\bf additions bit-\`a-bit} dans le calcul de $a \times b$.\\
Cela d\'epend \'evidemment de l'algorithme choisi~!

On fait

\[
	\underbrace{43 + 43 + \cdots + 43}_{\text{21 fois}}
\] 

\begin{align*}
	& 43 && \text{taille $\log(a)$} \\
	+ & 43 && \text{taille $\log(a+1)$} \\
	\vdots                           \\
	+ & 43 && \text{taille $\log(a+1)$}
\end{align*}

D'où $c_{a, b} = \Theta(b \lg a)$

\paragraph{Exemple moins naïf}

\begin{align*}
	&\quad \overline{43}^{10} = \overline{101011}^2 \\
	\times \\
	&\quad \overline{21}^{10} = \overline{010101}^2 \\
	= &\quad \overline{1110000111}^2
\end{align*}

% \begin{table}[h]
% 	\centering
% 	\begin{tabular}{ccccccccccc}
% 	  &  &  &  &  & 1 & 0 & 1 & 0 & 1 & 1 \\
% 	  &  & \\
% 	1 & 0 & 1 & 0 & 1 & 1 \\\hline
% 	  1&1&0&1&0&1&1&1 \\
% 	  1&0&1&0&1&1 \\\hline
% 	   &1&1&1&0&0&0&0&1&1&1
% 	\end{tabular}
% \end{table}

On a: 
\begin{align*}
	c_{a, b} &= \Theta((\log a + 1) + \cdots + (\log a + \log b)) \\
		 &= \Theta(\log a \log b)
\end{align*}
\xxe

On verra en TD \textbf{l'algorithme de Karastuba} qui permet de calculer plus efficacement un tel produit \`a l'aide d'une strat\'egie de type "diviser pour r\'egner".

\subsection{Factorielle}

\exx\ \\
On a vu plusieurs versions d'un algorithme de calcul de $n!$ mais ce sont diff\'erentes versions {\bf d'un m\^eme algorithme}.\megasubline
\xxe

Notons $c_n$ le nombre de {\bf multiplications} dans le calcul de $n!$.

\[
	f(n) := \begin{cases}
		1 & \text{si $n=0$} \\
		n\cdot f(n-1) & \text{sinon}
	\end{cases}
\] 

\begin{align*}
	c_0 &= 0 \\
	c_n &= 1  + c_{n-1} \\
	    &= 1 + 1 +c_{n-2} &&= 2 + c_{n-2} \\
	    &= 2 + 1 + c_{n-3} &&= 3 + c_{n-3} \\
	& \vdots \\
	&= n + c_0 && \fbox{c_n = n}
\end{align*}

\begin{align*}
	c_n &= \Theta(1) + c_{n-1} \\
	&= \Theta(1) + \Theta(n) + c_{n-1} \\
	&= \underbrace{\Theta(1) + \cdots + \Theta(1)}_{\text{$n$ fois}} + c_0 \\
	&= n\Theta(1) \\
	&= \Theta(n) \\
\end{align*}

\paragraph{Complexité en espace}
\[
	s_n = \Theta(1)
\] 

\subsection{ExponentiationS}


\exx\ \\
On a vu plusieurs algorithmes de calcul de $x^n$ et c'\'etaient vraiment {\bf des algorithmes diff\'erents}.

\[
x^n = \begin{cases}
	1 & \text{si $n = 0$} \\
	x\cdot x^{n-1} & \text{sinon}
\end{cases}
\] 

D'où

\begin{align*}
	c_n &= \begin{cases}
		0 & \text{si $n=0$} \\
		1+c_{n-1} & \text{sinon}
	\end{cases} \\
\end{align*}

On a $c_n = c_{n-1} + \Theta(1)$ d'où \[
	c_n = \Theta(n)
\] 

\paragraph{Exponentiation rapide}

\[
x^n := \begin{cases}
	1 & \text{si $n = 0$} \\
	x & \text{si $n = 1$} \\
	a\cdot a & \text{si $a \mod 2 = 0$ avec $a = x^{\frac{n}{2}}$} \\
	x\cdot a\cdot a & \text{si $a \mod 2 = 1$, avec  $a = x^{\floor{\frac{n}{2}}}$}

\end{cases}
\] 

Ainsi:
\begin{align*}
c_n &:= \begin{cases}
	0 & \text{si $n = 0$} \\
	0 & \text{si $n = 1$} \\
	1 + c_{\frac{n}{2}} & \text{si $a \mod 2 = 0$ avec $a = x^{\frac{n}{2}}$} \\
	2 + c_{\left\lfloor\frac{n}{2}\right\rfloor} & \text{si $a \mod 2 = 1$, avec  $a = x^{\floor{\frac{n}{2}}}$}
\end{cases} \\
&= \begin{cases}
	0 & \text{si $n \in \{0, 1\} $} \\
	2 + c_{\floor{\frac{n}{2}}} & \text{sinon}
\end{cases} \\
	\implies c_n &= c_{\floor{\frac{n}{2}}} + \Theta(1) \\
		     &= \Theta(1) + \Theta(1) + c_{\frac{n}{4}} && \text{à partir d'ici, on note $\frac{a}{b} := \floor{\frac{a}{b}}$}\\
		     &= \underbrace{\Theta(1) + \cdots + \Theta(1)}_{\text{$k$ fois}} + c_{\frac{n}{2^{k}}} \\
		     &= \underbrace{\Theta(1) + \cdots + \Theta(1)}_{\text{$k$ fois}} + c_{\text{0 ou 1}} && \text{pour $k = \ceil{\lg n}$} \\
		     &= \Theta(k) \\
		     &= \Theta(\ceil{\lg n}) \\
		     &= \Theta(\lg n) \\
\end{align*}

D'où $c_n = \Theta(\lg n)$

\paragraph{Exponentiation qui se croit rapide}

\[
x^{n} = \begin{cases}
	1 & \text{si $n \in \{0, 1\} $} \\
	x^{\frac{n}{2}}\cdot x^{\frac{n}{2}} & \text{si $n$ est pair} \\
	x\cdot x^{\frac{n}{2}}\cdot x^{\frac{n}{2}} & \text{si $n$ est impair} \\
\end{cases}
\] 

On a:

\begin{align*}
	c_n &= \mathbf{2} c_{\frac{n}{2}} + \Theta(1) \\
	    &= \Theta(1) + 2\Theta(1) + 4 c_{\frac{n}{4}} \\
	    &= \Theta(1) + 2\Theta(1) + 4\Theta(1) + 8 c_{\frac{n}{8}} \\
	    &\vdots \\
	    &= \Theta(1) + \cdots + 2^{k}\Theta(1) + 2^k c_{\frac{n}{2^k}} \\
	    &= \Theta(1+2+4+\cdots+2^k) + c_0 &&\text{pour $k = \ceil{\lg n}$} \\
	    &= \Theta(1) (2^{k+1}-1)+0 \\
	    &= \Theta(2^k 2 - 1) \\
	    &= \Theta(2^k) \\
	    &= \Theta(n) \\
\end{align*}

\paragraph{Complexité spatiale}
\[
	\Theta(1).
\] Youpie.

\xxe



\subsection{Tris}

\exx\ \\
On a vu plusieurs algorithmes de tris et c'\'etaient vraiment {\bf des algorithmes diff\'erents}.
\paragraph{Tri par insertion}

On a \[
	c_n = c_{n-1} + \Theta(1)
\] 

D'où \[
	c_n = \Theta(n^2)
\] 
\xxe


\paragraph{Tri par sélection}

C'est pareil, juste la \emph{sélection} est couteuse au lieu de l'\emph{insertion}

\[
	c_n = \Theta(n^2)
\] 

\paragraph{Tri par fusion}

Trois étapes:
\begin{enumerate}
	\item scission (coûte $n$ )
	\item les deux appels récursifs (coûte deux fos $c_{\frac{n}{2}}$)
	\item la fusion (coûte $n$ )
\end{enumerate}

D'où 

\begin{align*}
	c_n &= 2c_{\left\lceil \frac{n}{2} \right\rceil } + \Theta(n) \\
	    &= \Theta(n) + 2c_{\left\lceil \frac{n}{2} \right\rceil }  \\
	    &= \Theta(n) + 2\Theta(\frac{n}{2}) + 4 c_{\left\lceil \frac{n}{4} \right\rceil } \\
	    &= \Theta(n) + 2\Theta(\frac{n}{2})  + 4\Theta(\frac{n}{4}) + 8 c_{\left\lceil \frac{n}{8} \right\rceil } \\
	    &\vdots \\
	    &= \underbrace{\Theta(n) + \cdots + 2^k \Theta(\frac{n}{2^k})}_{\text{$k$ fois}} + \cancel{2^{k+1} c_0} \\
	    &= \underbrace{\Theta(n) + \cdots + \Theta(n)}_\text{$k$ fois} \\
	    &= \Theta(nk) \\
	    &= \Theta(n \lg n)
\end{align*}

\paragraph{Tri par pivot}


\emph{Dans le cas \ocaml{liste = []}} 

\begin{enumerate}
	\item scission: $n$ 
	\item deux appels récursifs: le pivot est le plus grand ou le plus petit, donc $c_{n-1}$ et $1$
	\item fusion
\end{enumerate}

On a $c_n = c_{n-1}+\Theta(1) = \Theta(n^2)$.

\emph{Dans le meilleurs cas (autant d'éléments supérieurs au pivot que inférieur)} 

Alors, les appels récursifs sont sur $floor{\frac{n}{2}}$.

On a ainsi \[
	c_n = 2c_{\floor{\frac{n}{2}}} + \Theta(n) = \Theta(n \lg n)
\] 

\subsection{Fibonacci}

\exx\ \\
On a vu plusieurs algorithmes de calcul de $F_n$ et c'\'etaient vraiment {\bf des algorithmes diff\'erents}.

On a $c_0 = c_1 = 1$ et pour $n\neq 0$, $c_n = c_{n-1} + c_{n-2} + 1$.

Même relation de récurrence que pour Fibonacci. Si on a le temps, on montre qu'on a $c_n = \Theta(F_n)$.

Un peu de maths: $F_n = \frac{1}{\sqrt{5} }\left( \phi^n + \left( \frac{-1}{\phi} \right)^n \right) $.

Conclusion, $c_n = \Theta(\phi^n)$
\xxe


\section{M\'ethodes de calcul g\'en\'erales}

\medskip

\subsection{It\'eration}

\rmq\ \\[-0.7cm]
Complexit\'e d'une composition~: un algorithme obtenu en appliquant successivement des algorithmes de complexit\'es $c_{1,n}$, $c_{2,n}$, $\ldots$, $c_{r,n}$ a pour complexit\'e $c_n=c_{1,{n_1}}+c_{2,{n_2}}+\cdots+c_{r,{n_r}}$.\megasubline\\
Ceci permet d'estimer la complexit\'e d'une boucle \`a l'aide du th\'eor\`eme suivant.
\qmr

\bigskip

\thm[Sommation de $O$ et de $\Theta$]
\ \\[-0.75cm]
\begin{enumerate}[$\bullet$]
\item $\dsp{\sum_{k=1}^n O(k^\alpha) = O(n^{\alpha+1})}$ et $\dsp{\sum_{k=1}^n \Theta(k^\alpha) = \Theta(n^{\alpha+1})}$.
\item $\dsp{\sum_{k=1}^n O(k^\alpha\lg^\beta(k)) = O(n^{\alpha+1}\lg^\beta(n))}$ et $\dsp{\sum_{k=1}^n \Theta(k^\alpha\lg^\beta(k)) = \Theta(n^{\alpha+1}\lg^\beta(n))}$.
\item Pour $\lambda>1$, $\dsp{\sum_{k=1}^n O(\lambda^k) = O(\lambda^{n+1})= O(\lambda^{n})}$.
\end{enumerate}
\mht


\medskip

\subsection{R\'ecursivit\'e}

\rmq\ \\[-0.7cm]
Complexit\'e d'une reconstruction~: en notant $c_n$ la complexit\'e d'un algorithme r\'ecursif avec appels r\'ecursifs est de la forme $f(n) = g(f(m_1),\ldots,f(m_r))$, on a $c_n = c_{m_1} + \cdots + c_{m_r} + d_m$ o\`u $d_m$ est le nombre d'op\'erations pour le calcul de $g(a_1,\ldots,a_r)$ une fois calcul\'es les $a_i=f(m_i)$.
\qmr

\bigskip

\thm[Suites r\'ecurrentes simples classiques]
\ \\[-0.75cm]
\begin{enumerate}[$\bullet$]
\item La r\'ecurrence $\dsp{c_{n}=c_{n-1}+\Theta(1)}$ conduit \`a $c_n=\Theta(n)$.
\item Pour $\alpha>0$, la r\'ecurrence $\dsp{c_{n}=c_{n-1} + \Theta\big(n^\alpha\big)}$ conduit \`a $c_n=\Theta\big(n^{\alpha+1}\big)$.
\item Pour $\lambda>1$, la r\'ecurrence $\dsp{c_{n}=\lambda c_{n-1} + O\big(n^\alpha\big)}$ conduit \`a $c_n=\Theta(\lambda^n)$.
\item Si $X^2-aX-b$ a deux racines $\lambda_1<\lambda_2$ alors la r\'ecurrence $\dsp{c_{n}=ac_{n-1}+bc_{n-2}+\gamma}$ conduit \`a $c_n=\Theta(\lambda_2^{{}^n})$.
\end{enumerate}
\mht


\exs \newpage
\sxe

\bigskip

\textbf{Strat\'egie "diviser pour r\'egner".}\\
On divise le probl\`eme en sous-probl\`emes de taille $\lfloor\frac{n}{\lambda}\rfloor$, on traite r\'ecursivement les sous-probl\`emes, on reconstruit la solution globale \`a l'aide des solutions partielles.
\begin{itemize}
\item co\^ut de la division en sous-probl\`emes~: d(n)
\item co\^ut d'un sous-probl\`eme~: $c_{\lfloor\frac{n}{\lambda}\rfloor}$
\item co\^ut de la reconstruction~: r(n)
\end{itemize}
Le co\^ut total est~: $c_n = a c_{\lfloor\frac{n}{\lambda}\rfloor} + f(n)$ o\`u $a$ est le nombre de sous-probl\`emes et $f(n)=d(n)+r(n)$.

\bigskip

\exs \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
\sxe


\thm[Strat\'egie "diviser pour r\'egner"]
\ \\[-0.75cm]
\begin{enumerate}[$\bullet$]
%\item La r\'ecurrence $\dsp{c_{n}=c_{\lfloor\frac{n}{2}\rfloor}+\Theta(1)}$ conduit \`a $c_n=\Theta(\lg(n))$.
\item La r\'ecurrence $\dsp{c_{n}=a\, c_{\lfloor\frac{n}{2}\rfloor}+\Theta(n^\beta)}$ conduit \`a
\begin{enumerate}
\item $c_n=\Theta(n^\alpha)=\Theta(a^{\lg(n)})$ si $\beta<\alpha=\lg(a)$.
\item $c_n=\Theta(n^\alpha\lg(n))=\Theta(\lg(n)a^{\lg(n)})$ si $\beta=\alpha=\lg(a)$.
\item $c_n=\Theta(n^\beta)$ si $\beta>\alpha=\lg(a)$.\subline
\end{enumerate}
\item Trois cas particuliers utiles~:\begin{enumerate}
\item La r\'ecurrence $\dsp{c_{n}=c_{\lfloor\frac{n}{2}\rfloor}+\Theta(1)}$ conduit \`a $c_n=\Theta(\lg(n))$.
\item Les r\'ecurrences $\dsp{c_{n}=2c_{\lfloor\frac{n}{2}\rfloor}+\Theta(1)}$  et 
%La r\'ecurrence 
$\dsp{c_{n}=c_{\lfloor\frac{n}{2}\rfloor}+c_{\lceil\frac{n}{2}\rceil}+\Theta(1)}$ conduisent \`a $c_n=\Theta(n)$.
\item Les r\'ecurrences $\dsp{c_{n}=2c_{\lfloor\frac{n}{2}\rfloor}+\Theta(n)}$  et 
%La r\'ecurrence 
$\dsp{c_{n}=c_{\lfloor\frac{n}{2}\rfloor}+c_{\lceil\frac{n}{2}\rceil}+\Theta(n)}$ conduisent \`a $c_n=\Theta(n\lg(n))$.
\end{enumerate}
\end{enumerate}
\mht
On retrouve les r\'esultats vus pr\'ec\'edemment.

\end{document}
