Se familiariser avec la complexité temporelle et spatiale

La complexité d'un algorithme est une mesure de l'efficacité de cet algorithme, généralement en termes de temps (complexité temporelle) et d'espace (complexité spatiale). Elle évalue comment les ressources nécessaires pour exécuter l'algorithme augmentent avec la taille de l'entrée.

Complexité spatiale

La complexité spatiale d'un algorithme représente la quantité de mémoire nécessaire pour exécuter cet algorithme en fonction de la taille de l'entrée.

Exemple de code en JavaScript montrant l'utilisation de l'espace mémoire :

// Exemple de calcul de la complexité spatiale avec une fonction qui stocke les carrés des nombres
function stockerCarres(n) {
    // Initialisation d'un tableau pour stocker les carrés
    let carres = [];
    // Boucle pour chaque entier de 1 à n
    for (let i = 1; i <= n; i++) {
        // Stockage du carré de i dans le tableau
        carres.push(i * i);
    }
    return carres;
}

// Stockage des carrés de 1 à 10
console.log(stockerCarres(10));  // Output: [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

Complexité Spatiale (Space Complexity)

Exemple amusant : La Pile de Livres

Supposons que tu veux empiler des livres. Si tu as 10 livres, tu as besoin d'un espace suffisant pour une pile de 10 livres. Si tu as 20 livres, tu as besoin du double d'espace. L'espace que tu utilises augmente proportionnellement au nombre de livres. C'est une complexité spatiale linéaire, notée $O(n)$.

// Empiler des livres avec une complexité spatiale linéaire
function empilerLivres(n) {
    let pile = [];
    for (let i = 0; i < n; i++) {
        pile.push(`Livre ${i + 1}`);
    }
    return pile;
}

console.log(empilerLivres(5));  // Output: ['Livre 1', 'Livre 2', 'Livre 3', 'Livre 4', 'Livre 5']

Autre exemple : Le Frigo Tetris

Imagine que tu dois ranger des plats dans ton frigo après un grand repas de famille. Plus il y a de plats, plus tu as besoin d'espace dans le frigo. Si tu as 10 plats, tu as besoin de plus de place que pour 5 plats. La quantité d'espace nécessaire augmente proportionnellement au nombre de plats. C'est aussi une complexité spatiale linéaire $O(n)$.

Ranger des Plats dans le Frigo avec Complexité Spatiale O

Imaginons que nous avons une fonction qui simule le rangement de plats dans un frigo après un grand repas de famille. Plus il y a de plats, plus nous avons besoin d'espace pour les ranger. La quantité d'espace nécessaire augmente proportionnellement au nombre de plats, ce qui illustre une complexité spatiale linéaire $O(n)$.

function rangerPlatsDansFrigo(nombreDePlats) {
    // Initialisation d'un tableau pour représenter les plats dans le frigo
    let frigo = [];

    // Boucle pour chaque plat
    for (let i = 1; i <= nombreDePlats; i++) {
        // Ajouter un plat au frigo
        frigo.push(`Plat ${i}`);
        console.log(`Rangement du Plat ${i} dans le frigo`);
    }

    // Retourner l'état final du frigo
    return frigo;
}

// Appel de la fonction pour ranger 5 plats dans le frigo
let frigoApresRepas = rangerPlatsDansFrigo(5);
console.log(frigoApresRepas);

// Output:
// Rangement du Plat 1 dans le frigo
// Rangement du Plat 2 dans le frigo
// Rangement du Plat 3 dans le frigo
// Rangement du Plat 4 dans le frigo
// Rangement du Plat 5 dans le frigo
// ["Plat 1", "Plat 2", "Plat 3", "Plat 4", "Plat 5"]

Explication

• Complexité Spatiale Linéaire $O(n)$ : La quantité d'espace (mémoire) utilisée par l'algorithme augmente proportionnellement au nombre de plats que l'on souhaite ranger dans le frigo. Si le nombre de plats double, la quantité d'espace nécessaire dans le tableau frigo double également.
• Simulation du Rangement : La fonction utilise une boucle pour ajouter chaque plat dans un tableau représentant le frigo. Pour chaque plat, elle affiche un message indiquant qu'un plat est rangé.
• Résultat Final : Le tableau frigo contient tous les plats rangés, montrant que l'espace utilisé par le tableau augmente linéairement avec le nombre de plats.

Ce code montre comment un algorithme avec une complexité spatiale linéaire fonctionne en pratique. La mémoire utilisée augmente de manière linéaire en fonction du nombre d'éléments à traiter, illustrant la relation directe entre la taille de l'entrée et l'utilisation des ressources.