\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}