3. Terminaison, correction et complexité d’un algorithme

Cf. TD1reponses

• Terminaison de l’algorithme : L’algorithme se termine t’il ? (oui/non)
• Correction : les données en sortie de l’algorithme sont-elles conforme au problème à résoudre (oui/non)
• Complexité : Combien d’opérations élémentaires l’algorithme effectue t’il ? Quelle place en mémoire occupe t’il ? (Suite numérique en fonction de “taille” de données)
  • Dans le pire des cas : On cherche un objet sur lequel l’algorithme effectuera le plus grand nombre d’opérations parmi tout les objets de taille n.
  • En moyenne : Une moyenne de nombre d’opérations selon une distribution de probabilités sur les objets de taille n. Souvent une distribution uniforme.

Exemple de tri “à bulle”

Entrée : Tableau d’entiers T de taille m
Sortie : Tableau d’entiers G triés selon l’ordre croissant. Il faut que G contienne les “mêmes” entiers que T.

void trie_a_bulle(int * T, int m) {
    int bool1 = 0;
    for(int i = 0; i < m; i++) {
        if (T[i] > T[i + 1]) {
            bool1 = 1;
            int tmp = T[i + 1];
            T[i + 1] = T[i];
            T[i] = tmp;
        }
    }
    if (bool1 != 0) return trie_a_bulle(T, m--);
}