Notion de base en algo (Complexité spatiale) Flashcards
(22 cards)
Qu’est-ce que la complexité spatiale d’un algorithme ?
La quantité de mémoire supplémentaire utilisée par l’algorithme en fonction de la taille de l’entrée (n), exprimée en notation O.
Quelle est la différence entre la pile (stack) et le tas (heap) en mémoire ?
Pile : Gérée automatiquement (LIFO), pour les variables locales et appels de fonctions. Taille fixe.
Tas : Gérée manuellement/dynamiquement, pour les données de taille variable. Taille flexible.
Pourquoi swap(a, b) a une complexité spatiale O(1) ?
Elle utilise 1 seule variable temporaire, quel que soit le type ou la taille de a et b.
L’espace mémoire est constant (ne dépend pas de n).
Pourquoi copier_tableau(arr) a une complexité spatiale O(n) ?
Parce qu’elle crée une copie du tableau (taille n).
Pourquoi une récursion profonde (ex: fibonacci(n)) a une complexité spatiale O(n) ?
Parce que chaque appel récursif empile un nouveau cadre de pile (jusqu’à n appels).
Pourquoi s += “a” dans une boucle n fois a une complexité spatiale **O(n²)` ?
Les strings étant immuables, chaque concaténation crée une nouvelle copie (coût cumulé quadratique).
Comment concaténer n strings en O(n) en espace ?
Utiliser ““.join(liste) pour éviter les copies intermédiaires.
Pourquoi une matrice n x n a une complexité spatiale O(n²) ?
Parce qu’elle stocke n² éléments.
Quel est le rôle du garbage collector dans la complexité spatiale ?
Il libère automatiquement la mémoire du tas quand les objets ne sont plus utilisés (évite les fuites).
Qu’est-ce qu’un stack overflow ?
Un crash causé par le dépassement de la taille maximale de la pile (ex: récursion infinie).
Pourquoi tri_fusion(arr) a une complexité spatiale O(n)?
Il alloue un tableau temporaire de taille n pour fusionner les sous-tableaux.
Quelle est la complexité spatiale d’un algorithme générant toutes les sous-parties d’un ensemble de taille n ?
O(2ⁿ) car il y a 2ⁿ sous-parties à stocker.
Comment analyser la complexité spatiale d’un algorithme ?
Compter les allocations mémoires explicites (tableaux, objets).
Évaluer la profondeur de la pile d'appels (récursions). Ignorer l'espace des entrées/sorties (sauf si modifié).
Qu’est-ce que la complexité spatiale en cas moyen ?
L’espace mémoire moyen utilisé pour des entrées aléatoires (ex: pile d’appels + tas).
Quelle est la complexité spatiale du tri par insertion dans le meilleur cas ?
O(1) (tri en place, aucune allocation supplémentaire).
Pourquoi la complexité spatiale de QuickSort est O(log n) en cas moyen ?
La profondeur de récursion moyenne est log n (pile d’appels).
Pourquoi s += “a” a une complexité spatiale O(n²) en cas moyen ?
Les copies temporaires de strings s’accumulent avant le garbage collection.
Quelle est la complexité spatiale d’un algorithme générant toutes les permutations d’un ensemble de taille n ?
O(n × n!) (stockage de n! permutations, chacune de taille n).
Comment réduire la complexité spatiale d’une récursion ?
Remplacer par une boucle itérative (ex: Fibonacci itératif → O(1)).
Donnez un exemple d’algo avec complexité spatiale O(n) dans le pire cas.
Tri Fusion → stocke des sous-tableaux temporaires.
Pourquoi une HashMap a une complexité spatiale moyenne O(n) ?
Stocke n éléments, mais avec des collisions gérées par des buckets (mémoire linéaire en moyenne).
