j

[cours-mesi.git] / complexite.tex

diff --git a/complexite.tex b/complexite.tex
index 4fdf00d8a2f7e29714be2c1206576b5786d4c1eb..6d66125ba533d9007322991cb77ee6cc0b066fab 100644 (file)
--- a/complexite.tex
+++ b/complexite.tex
@@ -36,7 +36,7 @@ $5n^3\leq 10.\dfrac{n^3}{2}$.
 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  
 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. 
+$\dfrac{n}{2} \leq c$ ce qui est impossible. 

 \end{itemize}
 
 
 \end{itemize}
 
 


@@ -200,7 +200,7 @@ On considère tout d'abord l'algorithme suivant:
  \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)$}
  \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)$}

- $a' = a$ \; \nllabel{laff1} 
+ $a' = a_n$ \; \nllabel{laff1} 

  \For{$i=n-1$ \KwTo $0$}{\nllabel{laford} 
     $a' = a_i + t \times a'$ \; \nllabel{lafori}
  \nllabel{laforf}}
  \For{$i=n-1$ \KwTo $0$}{\nllabel{laford} 
     $a' = a_i + t \times a'$ \; \nllabel{lafori}
  \nllabel{laforf}}


@@ -280,7 +280,7 @@ n & T_1(n) & T_2(n) \\
 \begin{enumerate}
 \item En déduire quel sera le temps nécessaire au traitement de données 
   de taille $n'=10^4$.
 \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}
 \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}