L'essentiel à connaître
La complexité algorithmique est l'outil fondamental qui te permet de mesurer l'efficacité d'un algorithme sans dépendre de la puissance de ta machine. On utilise principalement la notation Grand O (Big O) pour exprimer comment le temps d'exécution ou l'espace mémoire requis évolue à mesure que la taille des données d'entrée, notée n, augmente. C'est ce qu'on appelle la complexité asymptotique.
Pour bien réussir ce quiz, tu dois te souvenir des hiérarchies classiques. Un algorithme en O(1) est constant et ne dépend pas de la taille des données. À l'inverse, une complexité en O(n!) ou O(2^n) devient rapidement inutilisable dès que n dépasse quelques dizaines. Entre les deux, on retrouve les algorithmes de recherche et de tri que tu manipules au quotidien.
Définition : La complexité temporelle correspond au nombre d'opérations élémentaires effectuées par un algorithme en fonction de la taille n de l'entrée.
À retenir : En informatique, on s'intéresse généralement au pire des cas (worst case) pour garantir que l'algorithme ne dépassera jamais une certaine limite de temps.
Les points clés
L'analyse d'un algorithme demande de savoir identifier les boucles et les récursions. Une boucle simple parcourant un tableau de taille n est en O(n). Si tu imbriques une deuxième boucle parcourant également le tableau à l'intérieur de la première, tu obtiens une complexité quadratique en O(n²). C'est le cas typique des algorithmes de tri basiques comme le tri à bulles ou le tri par insertion.
Le Graal de l'optimisation est souvent la complexité logarithmique, O(log n). Elle apparaît dès que tu divises ton problème par deux à chaque étape, comme dans une recherche dichotomique. Comprendre cette progression est crucial car elle permet de traiter des millions de données en seulement quelques dizaines d'étapes. Fais attention aux constantes : O(2n) se simplifie toujours en O(n) car on ne garde que le terme dominant.
Formule : Hiérarchie de croissance : O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n) < O(n!).
Piège classique : Ne confonds pas la complexité temporelle (temps) et la complexité spatiale (mémoire vive utilisée). Un algorithme peut être très rapide mais consommer trop de RAM.
Quiz : Teste tes connaissances
Question 1 : Quelle est la complexité de l'accès à un élément précis dans un tableau via son index ?
Réponse : B. L'accès par index est direct car l'adresse mémoire est calculée instantanément. C'est une opération constante. L'option A (O(n)) correspondrait à une recherche d'un élément dont on ne connaît pas l'index dans un tableau non trié.
Question 2 : Tu effectues une recherche dichotomique dans un tableau trié de 1024 éléments. Combien d'étapes au maximum feras-tu ?
Réponse : C. La recherche dichotomique est en O(log n). Comme 2^10 = 1024, le logarithme en base 2 de 1024 est 10. Les options A et B sont beaucoup trop élevées pour cet algorithme très efficace.
Question 3 : Quelle est la complexité d'un algorithme contenant deux boucles imbriquées, chacune allant de 1 à n ?
Réponse : D. Pour chaque itération de la première boucle (n), la deuxième boucle s'exécute n fois. On multiplie donc n par n. L'option B est incorrecte car la notation O ignore les multiplicateurs constants et l'addition.
Question 4 : Si un algorithme a une complexité de O(n log n), comment s'appelle cette classe ?
Réponse : A. C'est la complexité classique des meilleurs algorithmes de tri (Merge Sort, Quick Sort). Logarithmique (B) serait O(log n) et Quadratique (D) serait O(n²).
Question 5 : Un algorithme met 1 seconde pour traiter 10 éléments avec une complexité de O(2^n). Combien de temps mettra-t-il pour 11 éléments ?
Réponse : C. Dans une complexité exponentielle de base 2, chaque fois que n augmente de 1, le temps de calcul double. Le passage de 2^10 à 2^11 multiplie le résultat par 2. L'option A serait vraie pour une complexité linéaire.
Question 6 : Lequel de ces algorithmes de tri possèd'une complexité de O(n log n) dans le pire des cas ?
Réponse : B. Le tri fusion garantit O(n log n) quel que soit l'état de la liste. Le Quick Sort (D) est souvent plus rapide en pratique mais peut tomber en O(n²) dans son pire cas si le pivot est mal choisi.
Question 7 : Que signifie "n" dans l'expression O(n) ?
Réponse : A. n représente la quantité d'informations que l'algorithme doit traiter (longueur d'une liste, nombre de nœuds d'un arbre). Sans cette variable, la notion de complexité n'aurait aucun sens.
Question 8 : Quelle complexité est considérée comme "intractable" (impossible à résoudre pour de grandes valeurs de n) ?
Réponse : D. La complexité factorielle croît de manière explosive. Pour n=20, n! est déjà supérieur à 2 quintillions. Les complexités polynomiales (A, C) sont lourdes mais restent calculables pour des n modérés.
Question 9 : Si tu simplifies O(3n² + 5n + 100), qu'obtiens-tu ?
Réponse : C. En analyse asymptotique, on ne garde que le terme de plus haut degré et on ignore les coefficients multiplicateurs. 3n² domine largement 5n et 100 quand n tend vers l'infini.
Question 10 : Quel est l'avantage principal d'un algorithme en O(log n) par rapport à O(n) ?
Réponse : A. Alors que O(n) croît linéairement, O(log n) croît extrêmement lentement. Pour n=1 000 000, O(n) fait un million d'opérations, alors que O(log n) n'en fait environ que 20.
Question 11 : Quelle est la complexité du parcours d'une matrice carrée de taille n x n ?
Réponse : B. Il y a n² éléments dans la matrice. Pour tous les visiter, il faut effectuer n x n opérations. C'est une complexité quadratique par rapport au côté de la matrice.
Question 12 : Dans quel cas la complexité spatiale est-elle O(n) pour stocker une liste ?
Réponse : C. La mémoire nécessaire est proportionnelle au nombre d'éléments stockés. Le tri (D) n'influence pas l'espace de stockage de base, seulement le temps de recherche ou l'organisation.
Comment ORBITECH Peut T'aider
ORBITECH AI Academy met à ta disposition des outils concrets pour réviser plus efficacement et progresser à ton rythme.
- Générateur de Quiz : crée des quiz personnalisés pour tester tes connaissances et identifier tes lacunes.
- Générateur d'Exercices : crée des exercices d'entraînement adaptés à ton niveau avec corrections détaillées.
- Générateur de Résumés : transforme tes cours en fiches de révision claires et structurées.
- Générateur de Mind Maps : visualise et organise tes idées avec des cartes mentales générées automatiquement.
Tous ces outils sont disponibles sur ta plateforme ORBITECH. Connecte-toi et explore ceux qui correspondent le mieux à tes besoins !