-\section{Complexité}
-\subsection{Quelques définitions}
+
+\section{Quelques définitions}
Soit $\mathcal{F}$ l'ensemble des fonctions de
$\N$ dans $\R^*_+$.
\large\}.
$$
Ainsi, à partir d'un rang $n_0$, $g(n)$ est majorée par $c f(n)$.
+On dit que \og $g$ est dans grand $\mathcal{O}$ de $f$ \fg{}.
\end{Def}
+On considère par exemple
+$f: n \mapsto \dfrac{n^3}{2}$,
+$g_1: n \mapsto n^2 + 17n + 15$ et
+$g_2: n \mapsto 5n^3$. On a:
+\begin{itemize}
+\item $g_1 \in \mathcal{O}(f)$: en effet, on prend $n_0 =1$ et
+$c = 2(1+17+15)$; alors
+$n^2+17n+15 \leq c.\dfrac{n^3}{2}$ si $n \geq 1$.
+\item $g_2 \in \mathcal{O}(f)$: en effet, on prend $n_0 =1$ et
+$c = 10$; alors
+$5n^3\leq 10.\dfrac{n^3}{2}$.
+\item $f \in \mathcal{O}(g_2)$: immédiat.
+\item $f \not \in \mathcal{O}(g_1)$: sinon on serait capable de trouver une
+constante $c$ telle que
+$\dfrac{n^3}{2} \leq c.(n^2 +17n + 5)$ soit encore
+$\dfrac{n^3}{2(n^2 +17n + 5)} \leq c$ et donc
+$\dfrac{n}{2} \leq c$ ce qui est impossible.
+\end{itemize}
+
+
+
+
\begin{Prop}
Soit $f$ et $g$ deux fonctions de $\mathcal{F}$. Si
$\lim_{n \rightarrow + \infty} \frac{f(n)}{g(n)} = l $
\end{Prop}
-\subsection{Mesurer la complexité}
+\section{Mesurer la complexité}
Soit $\mathcal{A}(n)$ un algorithme résolvant un problème sur des données
de taille $n$, $n \in \N$. On suppose que l'exécution de $\mathcal{A}$
coûte $T(n)$ étapes informatiques élémentaires ou unités de temps.
et lorsque
$T(n) \in \Theta(n^2)$, on dit que l'algorithme est \emph{quadratique en $n$}.
-\subsection{Exemples d'étude de complexité}
+\section{Exemples d'étude de complexité}
-\subsubsection{Un premier algo}
+\subsection{Un premier algo}
Soit $p$ une fonction polynôme de degré $n$ définie par
$
p(x) = \sum_{i=0}^n a_i x^i
\KwData{$n$: degré, $(a_i)_{0 \le i \le n}$: coefficients, $t$:
réel en lequel on évalue}
\KwResult{$\textit{val}$: réel tel que $\textit{val}= p(t)$}
- \nllabel{laff1} $a' = a$ \;
+ $a' = a_n$ \; \nllabel{laff1}
\For{$i=n-1$ \KwTo $0$}{\nllabel{laford}
- \nllabel{lafori} $a' = a_i + t \times a'$ \;
+ $a' = a_i + t \times a'$ \; \nllabel{lafori}
\nllabel{laforf}}
- \nllabel{laff2} $\textit{val} = a'$ \;
+$\textit{val} = a'$ \; \nllabel{laff2}
\caption{Évaluation du polynôme $p$ en $t$}
\end{algorithm}
Ainsi cet algorithme a une complexité linéaire en $n$.
-\subsubsection{Un second algo}
+\subsection{Un second algo}
On considère l'algorithme suivant:
\KwData{$n$: entier naturel, $(x_i)_{0 \le i \le n}$: abscisses réelles,
$(y_i)_{0 \le i \le n}$: ordonnées réelles.}
\KwResult{$d$: vecteur de $n+1$ réels}
- \nllabel{laford2}\For{$i=0$ \KwTo $n$}{
+ \For{$i=0$ \KwTo $n$} { \nllabel{laford2}
\nllabel{lafori2} $d_i' = y_i$ \;
- \nllabel{laforf2}}
- \nllabel{laford2b}\For{$i=1$ \KwTo $n$}{
+ }\nllabel{laforf2}
+ \For{$i=1$ \KwTo $n$}{\nllabel{laford2b}
\nllabel{laford2bb}\For{$j=n$ \KwTo $i$}{
\nllabel{lafori2bb} $d_j = (d_j - d_{j-1})/(x_j - x_{j-1})$ \;
\nllabel{laforf2b}}
- \nllabel{lafori2b} }
+ }\nllabel{lafori2b}
\caption{Polynôme d'approximation d'une fonction}
\end{algorithm}
\begin{enumerate}
\item En déduire quel sera le temps nécessaire au traitement de données
de taille $n'=10^4$.
-\item Même question avec $n'=200\lambda$ où $\lambda$ réel de $[1, +\infty[$.
+\item Même question avec $n'=200\lambda$ où $\lambda$ réel de $[0, +\infty[$.
\item Déterminer la taille maximale des données que peuvent traiter
$A_1$ et $A_2$ si le temps disponible est $t=10^5$.
\end{enumerate}
\end{enumerate}
\end{Exo}
-\subsection{Classes de complexité de problèmes}
+\section{Quelques classes de complexité de problèmes}
-\subsubsection{La classe \emph{P}}
+\subsection{La classe \emph{P}}
Les problèmes de cette classe sont ceux qui admettent une solution
algorithmique \emph{déterministe} et en temps \emph{polynomial}:
lorsque la taille du problème est $n$, le
-\subsubsection{La classe \emph{NP}}
+\subsection{La classe \emph{NP}}
Les problèmes de cette classe sont ceux qui admettent
une solution algorithmique \emph{non déterministe} en temps \emph{polynomial}.
De façon équivalente, c'est la classe des problèmes pour lesquels
si une solution est proposée, on peut vérifier sa validité à l'aide d'un
un algorithme en temps polynomial.
-On a $\emph{P} \subset \emph{NP}$.
+On a $\emph{P} \subseteq \emph{NP}$.
-\subsubsection{La classe \emph{NP-complet}}
+\subsection{La classe \emph{NP-complet}}
Les problèmes de cette classe sont ceux de la classe $\emph{NP}$
tels que tous les problèmes de la classe NP peuvent se réduire à celui-ci.
Cela signifie que le problème est au moins aussi difficile
