l'Algorithmie Avancée en Informatique: Découvrir quelques notations asymptotiques

Les notations asymptotiques sont utilisées pour décrire la complexité des algorithmes de manière approximative et pour comparer leur efficacité. Les principales notations sont O (grande-O), Ω (grande-Oméga) et Θ (grande-Theta).

2.4.1 O (grande-O)

La notation O (grande-O) décrit une limite supérieure asymptotique pour la complexité temporelle ou spatiale d'un algorithme. Elle donne une estimation du pire des cas.

Exemple : Si un algorithme a une complexité temporelle de O(n²), cela signifie que le temps d'exécution de l'algorithme augmente au plus comme le carré de la taille de l'entrée.

2.4.2 Ω (grande-Oméga)

La notation Ω (grande-Oméga) décrit une limite inférieure asymptotique pour la complexité d'un algorithme. Elle donne une estimation du meilleur des cas.

Exemple : Si un algorithme a une complexité temporelle de $Ω (n)$ , cela signifie que le temps d'exécution de l'algorithme augmente au moins linéairement avec la taille de l'entrée.

2.4.3 Θ (grande-Theta)

La notation Θ (grande-Theta) décrit une borne asymptotique exacte pour la complexité d'un algorithme. Elle donne une estimation à la fois de la limite supérieure et inférieure.

Exemple : Si un algorithme a une complexité temporelle de Θ(n log n) avec la taille de l'entrée.

Exemples de code pour illustrer les notations asymptotiques

// Fonction avec complexité O(n)
function fonctionLineaire(n) {
    for (let i = 0; i < n; i++) {
        console.log(i);
    }
}

// Fonction avec complexité O(n^2)
function fonctionQuadratique(n) {
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            console.log(i, j);
    }
  }
}

// Fonction avec complexité O(log n)
function fonctionLogarithmique(n) {
    let i = 1;
    while (i < n) {
        console.log(i);
        i = i * 2;
    }
}

// Fonction avec complexité O(n log n)
function fonctionLineaireLogarithmique(n) {
    for (let i = 0; i < n; i++) {
        let j = 1;
        while (j < n) {
            console.log(i, j);
            j = j * 2;
        }
    }
}

// Appel des fonctions pour des exemples
console.log("Fonction linéaire:");
fonctionLineaire(5);  // Output: 0, 1, 2, 3, 4

console.log("Fonction quadratique:");
fonctionQuadratique(3);  // Output: Paires (0,0) à (2,2)

console.log("Fonction logarithmique:");
fonctionLogarithmique(16);  // Output: 1, 2, 4, 8

console.log("Fonction linéaire logarithmique:");
fonctionLineaireLogarithmique(4);  // Output: Plusieurs paires (i,j) avec j étant puissance de 2

Notations Asymptotiques avec des Exemples

O (grande-O) : Limite Supérieure

Exemple : Le Tour de Manège

Imagine que tu dois faire un tour de manège et que le temps maximum pour un tour est de 5 minutes, peu importe combien de fois tu montes et descends du manège. Même si tu prends plus de temps à monter parfois, le pire des cas est toujours 5 minutes par tour. En algorithmie, c'est une notation $O (1)$ car le temps est constant.

Exemple de Code : Tour de Manège avec Complexité O(1)

Imaginons que nous avons une fonction qui simule un tour de manège. Peu importe le nombre de tours que vous faites ou le temps que vous mettez à monter et descendre du manège, chaque tour prendra toujours un maximum de 5 minutes. Cette situation illustre une complexité constante $O (1)$ .

function tourDeManège(nombreDeTours) {
    const TEMPS_PAR_TOUR = 5; // Temps maximum par tour en minutes

    for (let i = 1; i <= nombreDeTours; i++) {
        console.log(`Tour ${i}: Le manège tourne pour ${TEMPS_PAR_TOUR} minutes`);
    }
}

// Appel de la fonction pour 3 tours de manège
tourDeManège(3);

// Output:
// Tour 1: Le manège tourne pour 5 minutes
// Tour 2: Le manège tourne pour 5 minutes
// Tour 3: Le manège tourne pour 5 minutes

Explication

Complexité Temporelle Constante $O (1)$ : Peu importe combien de fois la fonction tourDeManège est appelée, chaque tour prend toujours exactement 5 minutes. Le temps d'exécution de chaque tour est constant et ne dépend pas de la taille de l'entrée.
Simulation des Tours : La fonction utilise une boucle pour simuler plusieurs tours de manège. Pour chaque tour, elle affiche un message indiquant que le manège tourne pour 5 minutes.

Ce code montre comment un algorithme avec une complexité constante fonctionne en pratique. Chaque appel à la fonction de tour prend un temps fixe et indépendant du nombre de tours demandés.

Ω (grande-Oméga) : Limite Inférieure

Exemple : La Course de L'escargot

Imagine que tu regardes une course d'escargots. Peu importe ce qui se passe, un escargot mettra toujours au moins 10 minutes pour parcourir un mètre. Même s'il y a des obstacles, il ne peut pas aller plus vite que ça. C'est une notation $Ω (1)$ car le temps minimum est constant.

Exemple de Code : Course de l'Escargot avec Complexité Ω(1)

Imaginons que nous avons une fonction qui simule une course d'escargots. Peu importe les conditions ou les obstacles, un escargot mettra toujours au moins 10 minutes pour parcourir un mètre. Cela illustre une complexité temporelle avec une limite inférieure constante $Ω (1)$ .

function courseEscargot(distanceEnMetres) {
    const TEMPS_PAR_METRE = 10; // Temps minimum pour parcourir un mètre en minutes

    // Boucle pour chaque mètre parcouru
    for (let i = 1; i <= distanceEnMetres; i++) {
        console.log(`L'escargot a parcouru ${i} mètre(s) en ${TEMPS_PAR_METRE} minutes`);
    }
}

// Appel de la fonction pour une distance de 5 mètres
courseEscargot(5);

// Output:
// L'escargot a parcouru 1 mètre(s) en 10 minutes
// L'escargot a parcouru 2 mètre(s) en 10 minutes
// L'escargot a parcouru 3 mètre(s) en 10 minutes
// L'escargot a parcouru 4 mètre(s) en 10 minutes
// L'escargot a parcouru 5 mètre(s) en 10 minutes

Explication

Complexité Temporelle $Ω (1)$ : La notation $Ω (1)$ indique que le temps minimum nécessaire pour l'escargot pour parcourir chaque mètre est constant, indépendamment des autres facteurs. Ici, c'est 10 minutes par mètre, ce qui ne peut pas être réduit.
Simulation de la Course : La fonction utilise une boucle pour simuler chaque mètre parcouru par l'escargot. À chaque mètre, elle affiche un message indiquant que l'escargot a mis 10 minutes pour parcourir cette distance.
Résultat Final : Le temps total pour parcourir la distance est directement proportionnel au nombre de mètres, mais le temps minimum pour chaque mètre est constant.

Ce code illustre comment la limite inférieure de la complexité temporelle $Ω (1)$ fonctionne en pratique. Chaque opération (ici, chaque mètre parcouru) prend au moins un temps constant, montrant que même dans le meilleur des cas, le temps par mètre ne peut être réduit en dessous de ce minimum constant.

Θ (grande-Theta) : Borne Asymptotique Exacte

Exemple : La Lutte Contre la Gravité

Imagine que tu fais du trampoline. À chaque saut, tu montes et descends, et tu passes exactement 2 secondes dans les airs. Peu importe ce qui se passe, chaque saut prend 2 secondes. C'est une notation $Θ (1)$ car le temps est exactement constant.

Exemple de Code : Sauts en Trampoline avec Complexité Θ(1)

Imaginons que nous avons une fonction qui simule des sauts en trampoline. Chaque saut prend exactement 2 secondes pour monter et descendre, indépendamment des conditions extérieures. Cela illustre une complexité temporelle avec une borne asymptotique exacte $Θ (1)$ .

function sautsEnTrampoline(nombreDeSauts) {
    const TEMPS_PAR_SAUT = 2; // Temps constant par saut en secondes

    // Boucle pour chaque saut
    for (let i = 1; i <= nombreDeSauts; i++) {
        console.log(`Saut ${i}: Tu passes exactement ${TEMPS_PAR_SAUT} secondes dans les airs`);
    }
}

// Appel de la fonction pour 5 sauts en trampoline
sautsEnTrampoline(5);

// Output:
// Saut 1: Tu passes exactement 2 secondes dans les airs
// Saut 2: Tu passes exactement 2 secondes dans les airs
// Saut 3: Tu passes exactement 2 secondes dans les airs
// Saut 4: Tu passes exactement 2 secondes dans les airs
// Saut 5: Tu passes exactement 2 secondes dans les airs

Explication

Complexité Temporelle $Θ (1)$ : La notation $Θ (1)$ indique que chaque opération (chaque saut en trampoline) prend exactement un temps constant, ici 2 secondes. Cela signifie que le temps est exactement constant et ne change pas avec la taille de l'entrée ou les conditions.
Simulation des Sauts : La fonction utilise une boucle pour simuler plusieurs sauts en trampoline. À chaque saut, elle affiche un message indiquant que le saut prend exactement 2 secondes.
Résultat Final : Chaque saut prend toujours exactement 2 secondes, indépendamment du nombre total de sauts effectués.

Ce code montre comment un algorithme avec une complexité temporelle $Θ (1)$ fonctionne en pratique. Chaque opération prend un temps constant et précis, illustrant que la durée de chaque saut est fixe et invariable, peu importe le nombre de sauts ou les circonstances.

Modifié le: mardi 18 février 2025, 05:44