Rappel de cours

Pour un algorithme donné, on souhaite déterminer le nombre d’instructions de base ou la quantité de donnée $T(n)$ qui seront effectuées ou utilisées dans le pire des cas, pour une entrée de taille $n$ (où $T : \mathbb{N} \to \mathbb{N}$).

• La taille est le nombre de bits nécessaires pour représenter l’entrée, généralement on simplie en byte/octet : unité indivisible en informatique (on ne peu pas stocké que des multiples d’octets). On considère généralement qu’un nombre a une taille constante (char, int, long, float …) et un tableau a donc une taille proportionnelle à sa longueur (N * sizeof(type)).
• Les instructions de base sont : les affectations, les opérations mathématiques, les comparaisons, l’accès à un élément de tableau… et on considère que chacune prend une unité de temps. Attention il y a des pieges !!!

Pour déterminé modéliser ce nombre, on cherche a définir des fonctions asymptotiques qui permettent d’encadrer la fonction. Donc soit en borne supérieur, soit inférieur. Cela permet de comprendre rapidement les meilleurs cas et les pires cas. On utilise alors les notations asymptotiques.

Étant données deux fonctions $f, g : \mathbb{N} \to \mathbb{N}$ :

• $f(n) \in O(g(n))$ : Borne supérieure : il existe $c > 0$ et $r \in \mathbb{N}$ tels que pour tout $i \geq r$, $f(i) \leq c \cdot g(i)$. Autrement dit, $f$ ne croît pas plus vite que $g$ à un facteur constant près.
• $f(n) \in \Omega(g(n))$ : Borne inférieure : il existe $c > 0$ et $r \in \mathbb{N}$ tels que pour tout $i \geq r$, $f(i) \geq c \cdot g(i)$. Autrement dit, $f$ ne croît pas moins vite que $g$.
• $f(n) \in \Theta(g(n))$ : Borne exacte : $f(n) \in O(g(n))$ et $f(n) \in \Omega(g(n))$. Les deux fonctions ont le même ordre de croissance.

Pour le calcule, globalement cela correspond a simplement compter. Pour simplifier on calculeras d’abors en profondeur t on remonte en appliquant des règles de calcul:

• Séquence : si un bloc A est en $O(f(n))$ et un bloc B est en $O(g(n))$,
  alors l’exécution de A puis B est en $O(\max(f(n), g(n)))$.
  • exemple : $A = n^3$ et $B = 2n + 5$ alors borne en $O(n^3)$
• Boucle simple : une boucle qui itère $n$ fois avec un corps en $O(1)$ donne $O(n)$.
• Boucles imbriquées : on multiplie les complexités de chaque boucle.
• Récursivité : on pose une relation de récurrence sur $T(n)$ et on la résout.

Une fois les complextités établie on range l’algorithme dans une classe de complexité :

Exercices mathématiques

Estimation et contraintes temporels

Complétez les tableaux suivants.

• Calculer le nombre d’opérations nécessaires pour exécuter l’algorithme en fonction :
  • de sa complexité
  • de la taille d’instance ( n )
• Calculer le temps d’exécution correspondant en supposant un ordinateur capable d’effectuer ( 10^9 ) opérations par seconde.
• Déterminer la plus grande instance du problème traitable dans un temps donné.

En supposant :

• $1 ,\mu s = 10^{-6} , s$
• $1 , ns = 10^{-9} , s$

Classification de fonctions

Classer chacune des fonctions suivantes dans la classe de complexité qui lui correspond parmi : $\Theta(1)$, $\Theta(\log n)$, $\Theta(n)$, $\Theta(n^2)$, $\Theta(n^c)$ pour $c \geq 1$, $\Theta(c^n)$ pour $c > 1$ :

Propriété de la somme

Soient $f_1 \in \Theta(g_1)$ et $f_2 \in \Theta(g_2)$.

• Exprimer la complexité asymptotique de $f_1 + f_2$ en fonction de $g_1$ et $g_2$.
• Le démontrer rigoureusement à partir des définitions.
• Retrouver logiquement $O(f(n) + g(n)) = O(\max(f(n), g(n)))$

Vrai ou Faux

Pour chaque assertion, indiquer si elle est vraie ou fausse et justifier :

• $3n^2 + 4n + 6 \in O(n^2)$
• $n^3 \in O(n^2)$
• $n \in \Omega(n^2)$
• $2^n \in \Theta(3^n)$
• $n^2 + 5n \in \Theta(n^2)$
• Pour tout entier fixé $k > 0$, $n^k \in O(2^n)$

Analyse de complexité itératifs

Somme des éléments d’un tableau

Analyser la complexité en temps $T(n)$ de ces deux versions de la fonction somme, où n est la taille du tableau.

int somme(int tab[], int n) {
  int s = 0;
  for (int i = 0; i < n; i++)
    s = s + tab[i];
  return s;
}

int somme(int tab[], int n) {
    int s = 0;
    while (n > 0) { 
        s += tab[n-1]; 
        n--;
    }
    return s;
}

• Compter précisément le nombre d’opérations élémentaires (affectations, comparaisons, additions, accès tableau).
• En déduire $T(n)$ puis la complexité asymptotique.
• Différence théorique et pratique ?

Recherche du maximum

Analyser la complexité dans le pire cas de la fonction suivante :

int maximum(int tab[], int n) {
  int max = tab;
  for (int i = 1; i < n; i++)
    if (tab[i] > max)
      max = tab[i];
  return max;
}

• Combien de comparaisons sont effectuées dans tous les cas ?
• Combien d’affectations sont effectuées dans le pire cas ? Quel est ce pire cas ?
• Donner $T(n)$ et la complexité asymptotique.

Recherche d’un élément

Analysez ses différentes versions :

int recherche_a(int tab[], int n, int x) {
  int index = -1;
  for (int i = 0; i < n; i++)
    if (tab[i] == x)
      index = i;
  return index;
}

int recherche_b(int tab[], int n, int x) {
  for (int i = 0; i < n; i++)
    if (tab[i] == x)
      return i;
  return -1;
}

int recherche_c(int tab[], int n, int x) {
  int index = -1;
  for (int i = 0; i < n; i++)
      index = i * (tab[i] == x) + index * (tab[i] != x);
  return index;
}

• Quelle est la complexité dans le meilleur cas ? Quand se produit-il ?
• Quelle est la complexité dans le pire cas ? Quand se produit-il ?
• Attention branch-miss prédiction : 15-30 cycles cpu

Boucles imbriquées

Déterminer la complexité asymptotique de chacune des fonctions suivantes :

Fonction A :

void fonctionA(int n) {
  int count = 0;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      count++;
}

Fonction B :

void fonctionB(int n) {
  int count = 0;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < i; j++)
      count++;
}

Fonction C :

void fonctionC(int n) {
  int count = 0;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      for (int k = 0; k < n; k++)
        count++;
}

• Pour chaque fonction, compter le nombre d’exécutions de count++.
• En déduire la complexité asymptotique de chaque fonction.

Division de l’espace

int compteur(int n) {
  int count = 0;
  int i = n;
  while (i > 0) {
    count++;
    i = i / 2;
  }
  return count;
}

• Pour $n = 16$, lister les valeurs successives de i.
• Exprimer le nombre d’itérations en fonction de $n$.
• En déduire la complexité asymptotique.

Tri à bulles (Bubble Sort)

Voici l’implémentation du tri à bulles en C :

void tri_bulles(int tab[], int n) {
  for (int i = n - 1; i >= 1; i--) {
    for (int j = 0; j < i; j++) {
      if (tab[j + 1] < tab[j]) {
        int tmp = tab[j];
        tab[j] = tab[j + 1];
        tab[j + 1] = tmp;
      }
    }
  }
}

• Combien de comparaisons sont effectuées au total (indépendamment des données) ?
• Combien d’échanges (swap) sont effectués dans le pire cas ? Quel est ce pire cas ?
• En déduire la complexité asymptotique du tri à bulles dans le pire cas.
• Quelle est la complexité dans le meilleur cas (tableau déjà trié) ? Le nombre de comparaisons change-t-il ?