\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^3}{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$ \; \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}
\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}$
