# L3S5 MATH - INFORMATIQUE S5 — UNIVERSITÉ DE STRASBOURG
## TP 3 — Complexité des algorithmes

**Remarques :**

- Quand on parlera de la complexité d'un algorithme, on sous-entendra sa complexité dans le pire des cas.
- On s'intéresse ici à la complexité arithmétique des algorithmes, celle correspondant au nombre d'affectations, de comparaisons et d'opérations arithmétiques.

**Exercice 1 – Notation $\mathcal{O}$ :**

(a) Rappeler la définition de $\mathcal{O}(1)$, $\mathcal{O}(2)$ et $\mathcal{O}(g)$ pour une fonction $g : \mathbb{N} \to \mathbb{R}$.

(b) Quelle est la différence entre $\mathcal{O}(1)$ et $\mathcal{O}(2)$ ?

(c) Quelle est la différence entre $\mathcal{O}(n^2 + n^3)$ et $\mathcal{O}(n^3)$ ?

**Exercice 2 :** On suppose que chacune des expressions ci-dessous donne le temps de calcul $T(n)$ nécessaire à un algorithme pour résoudre un problème de taille $n$. Pour chaque expression ci-dessous, déterminer les termes ayant la vitesse de croissance la plus faible et la plus forte, et donner leur notation « grand O ».

(a) $n^4/1000 + 100n^3 - 100n + 18$

(b) $6 + 0.001n^2 + 0.33n$

(c) $0.3n + 5n^{3.3} + 2.5n^{2.74}$

(d) $0.001n + 0.5n^{1.25}$

(e) $n^4 + n^3 \log(n)$

**Exercice 3 :** On souhaite simuler un compteur d'opérations arithmétiques pour vérifier que nos implémentations vérifient nos analyses de complexité.

(a) Définissez une fonction de prototype

```cpp
int mul( int a, int b )
```

retournant le résultat de la multiplication de a et b et incrémentant une variable globale pour garder le compte des multiplications réalisées dans un programme ; testez cette fonction dans un main.

(b) Proposez et implémentez un algorithme pour calculer $a^b$ quand $b$ est une puissance de 2, de complexité logarithmique en $b$. Testez cette fonction dans le main, et utilisez le compteur de multiplications pour vérifier que votre implémentation vérifie la complexité logarithmique.

**Exercice 4 :** On considère l'algorithme :

**Input** : Un entier $n \in \mathbb{N}$

```
1  total ← 0
2  for i from 1 to n - 1 do
3      for j from 1 to n - 1 do
4          total ← total + 1
5  return total
```

(a) Que calcule-t-il ?

(b) Comptez le nombre d'opérations (affectations, comparaisons et opération arithmétiques) sur des entiers de cet algorithme.

(c) Donnez le coût $T(n)$ en nombre d'opérations sur des entiers en fonction de $n$ de cet algorithme, et sa classe de complexité arithmétique.

(d) Proposez un algorithme avec une complexité arithmétique d'un plus petit ordre de grandeur réalisant la même tâche.

**Exercice 5 – Factorielle :** La définition mathématique de la fonction factorielle est, pour tout $n \in \mathbb{N}$ :

$$ n! := \prod_{k=1}^{n} k \quad \text{avec} \quad 0! := 1. $$

On propose l'algorithme **récursif** suivant pour calculer $n!$ :

**Algorithme 1 : FACTORIELLE_RÉCURSIVE — Calcul de $n!$ par méthode récursive**

**Input** : Un entier $n \in \mathbb{N}$

**Output** : Le calcul de $n!$

```
FACTORIELLE_RÉCURSIVE(n)
1  if n > 1 then
2      return n * FACTORIELLE_RÉCURSIVE(n - 1)
3  else
4      return 1
```

(a) Montrer par récurrence que l'algorithme calcule bien une factorielle.

(b) Quel est le domaine de définition de la variable d'entrée $n$ de l'algorithme ? Que se passe-t-il si $n$ est en dehors de son domaine de définition ?

(c) Quelle est la complexité arithmétique de l'algorithme ?

(d) Implémenter cet algorithme en C++ pour calculer la factorielle d'un entier $n \geq 0$. Tester cette fonction jusqu'à $20!$.

(e) Implémenter un autre algorithme, cette fois **itératif**, qui calcule la factorielle d'un entier $n \geq 0$. Tester ce nouvel algorithme et comparer son temps de calcul avec le temps de calcul de l'algorithme récursif. On pourra utiliser la librairie `ctime`, de la façon suivante :

```cpp
#include <ctime>
time_t start_clock, end_clock;
start_clock = clock();
/* code à tester */
end_clock = clock();
std::cout << "temps d'exécution : " << difftime(end_clock, start_clock) << std::endl;
```

**Exercice 6 :**

- Proposer un algorithme permettant de calculer les coefficients de la somme $P + Q$ de deux polynômes $P$ et $Q$ de même degré $n$. Quelle est la complexité arithmétique de cet algorithme ?
- Cet algorithme est-il optimal, *i.e.* peut-il exister un algorithme avec une meilleure complexité (sous-linéaire) pour additionner deux polynômes de degré $n$ donnés par leurs $n$ coefficients ?
- Implémenter cet algorithme en C++.

**Exercice 7 – Évaluation d'un polynôme :**

(a) Proposer un algorithme permettant d'évaluer un polynôme $P(x)$ de degré $n$ en un $x \in \mathbb{R}$ donné. Donner le nombre d'additions $A(n)$ et le nombre de multiplications $M(n)$ effectuées par cet algorithme.

(b) (**Méthode de Horner**) La méthode de Horner consiste à écrire un polynôme $P(x) = a_0 + \sum_{1 \le i \le n} a_i x^i$ de la façon suivante :

$$ P(x) = a_0 + x \left( a_1 + \dots x \left( a_{n-1} + a_n x \right) \dots \right). $$

Ainsi, le polynôme

$$ P(x) = 1 + 2x - 6x^2 + 3x^3 + x^4 $$

s'écrira

$$ P(x) = 1 + x \left( 2 + x \left( -6 + x \left( 3 + x \right) \right) \right). $$

Écrire un algorithme utilisant cette astuce pour évaluer un polynôme de degré $n$ en un $x \in \mathbb{R}$. Donner le nombre d'additions $A(n)$ et le nombre de multiplications $M(n)$ effectuées par cet algorithme.

(c) Implémenter les deux algorithmes en C++ et comparer les temps de calcul.

**Exercice 8 – Suite de Fibonacci :** On rappelle que la suite de Fibonacci est définie de la façon suivante :

$$ \begin{cases} F_0 = 1, F_1 = 1, \\ F_{n+2} = F_{n+1} + F_n \text{ pour tout } n \in \mathbb{N} \end{cases} $$

(a) Proposer deux algorithmes, l'un récursif et l'autre itératif, permettant de calculer les termes de la suite de Fibonacci. Donner la complexité arithmétique des deux algorithmes.

*Indice :* On pourra admettre la propriété suivante : pour toute suite de la forme $u_{n+2} = u_{n+1} + u_n + a$, on a

$$ \lim_{n \to +\infty} \frac{u_{n+1}}{u_n} = \varphi = \frac{1 + \sqrt{5}}{2} \approx 1.618. $$

(b) Implémenter les deux algorithmes en C++. Comparer les temps de calcul de chaque algorithme.

**Exercice 9 :**

- Proposer un algorithme permettant de calculer les coefficients du produit $PQ$ de deux polynômes $P$ et $Q$ de même degré $n$. Quelle est la complexité arithmétique de cet algorithme ?
- Cet algorithme est-il optimal, *i.e.* peut-il exister un algorithme avec une meilleure complexité (sous-quadratique) pour multiplier deux polynômes de degré $n$ donnés par leurs $n$ coefficients ?
- Implémenter cet algorithme en C++.