\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 $
\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}
\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}
-\section{Classes de complexité de problèmes}
+\section{Quelques classes de complexité de problèmes}
\subsection{La classe \emph{P}}
Les problèmes de cette classe sont ceux qui admettent une solution
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}$.
\subsection{La classe \emph{NP-complet}}
Les problèmes de cette classe sont ceux de la classe $\emph{NP}$
