Différences
Ci-dessous, les différences entre deux révisions de la page.
| Les deux révisions précédentes Révision précédente Prochaine révision | Révision précédente | ||
| tc_info:2020_cpp_1-3-1 [2020/09/30 11:36] – pprea | tc_info:2020_cpp_1-3-1 [2020/10/01 09:49] (Version actuelle) – pprea | ||
|---|---|---|---|
| Ligne 1: | Ligne 1: | ||
| + | Cet algorithme semble polynomial. En fait, ce n'est pas du tout le cas. | ||
| + | La complexité d'une algorithme n'est pas simplement le nombre d' | ||
| + | |||
| + | Ici, la taille des données est le nombre de chiffres que l'on utilise pour noter $x$ & $y$, c'est à dire $\log x + \log y$ (la base du $\log$ est la base dans laquelle on compte). | ||
| + | \\ | ||
| + | Si on note $n_y$ le nombre de chiffres de $y$, on voit que cet algorithme est en $O(2^{n_y})$, | ||