Exercice 1

Question 1

Pour $T1(n) = 9n²$ : Le terme dominant est $n²$. En ignorant la constante $9$, la complexité est $O(n²)$.
Pour $T2(n) = 100n + 96$ : Le terme dominant est $n$. En ignorant la constante $100$ et le terme additif $96$, la complexité est $O(n)$.

Question 2

Une complexité linéaire ($O(n)$) est asymptotiquement meilleure qu'une complexité quadratique ($O(n²)$). Pour des valeurs de n suffisamment grandes, l'algorithme A2 sera toujours plus rapide que A1.

Question 3

Pour A1 ($T1(n) = 9n$²) en $O(n²)$ : Il faut trouver $c$ et $n_0$ tels que $9n² ≤ c \times n²$ pour tout $n ≥ n0$.
- On choisi $c = 9$ et $n_0 = 1$.
- L'inégalité $9n² ≤ 9n²$ est toujours vraie pour tout $n ≥ 1$. La proposition est donc démontrée.
Pour A2 ($T2(n) = 100n + 96$) en $O(n)$ : On doit trouver $c$ et $n_0$ tels que $100n + 96 ≤ c \times n$ pour tout $n ≥ n0$.

Exercice 2

Variante 1: Avec décalage

On parcourt le tableau. Chaque fois qu'un zéro est trouvé à l'indice i, on décale tous les éléments de i+1 à n-1 d'une position vers la gauche. Cette opération écrase le zéro. Pour conserver le nombre d'éléments, un zéro est ensuite ajouté à la fin du tableau.

Variante 2: Deux pointeurs

On utilise une variable, index_non_nul, initialisée à 0, qui conserve la position où le prochain élément non nul doit être inséré. On parcourt le tableau une seule fois. Si l'élément courant n'est pas un zéro, on le place à la position ndex_non_nul et on incrémente cet index.

Après ce premier parcours, index_non_nul contient le nombre d'éléments non nuls. Le reste du tableau (de l'indice index_non_nul à n-1) est alors rempli de zéros. Le nombre de zéros, k, est simplement n - index_non_nul.

script python calcul