Self-assessment quiz

# Qu’est-ce que la complexité algorithmique ? - [ ] Une mesure du temps d’exécution d’un algorithme > ❌ La complexité algorithmique mesure non seulement le temps d'exécution, mais aussi l'espace mémoire utilisé par un algorithme. - [ ] Une mesure de l’espace mémoire utilisé par un algorithme > ❌ La complexité algorithmique prend en compte à la fois l'espace mémoire et le temps d'exécution de l'algorithme. - [x] Une mesure du temps d’exécution et de la mémoire utilisée par un algorithme > ✅ La complexité algorithmique mesure à la fois le temps d'exécution et l'espace mémoire nécessaire à un algorithme. - [ ] Une mesure de la complexité d’un algorithme > ❌ La complexité algorithmique ne mesure pas la difficulté de compréhension de l'algorithme, mais bien les ressources qu'il consomme. # Qu’est-ce qui nous intéresse généralement quand on étudie la complexité algorithmique ? - [ ] L’analyse moyenne > ❌ L'analyse moyenne peut être utile, mais on se concentre souvent sur le pire des cas pour garantir la performance de l'algorithme dans toutes les situations. - [ ] L’analyse cas par cas > ❌ La complexité algorithmique est justement là pour éviter de faire du cas par cas et donner une analyse générale. - [x] L’analyse du pire des cas > ✅ L'analyse du pire des cas est utilisée pour s'assurer qu'un algorithme fonctionnera dans des délais raisonnables, même dans les situations les plus défavorables. # Laquelle des notations suivantes correspond aux algorithmes linéaires et logarithmiques ? - [ ] $O(n)$ > ❌ O(n) représente une complexité linéaire, sans le composant logarithmique. - [x] $O(n \cdot log(n))$ > ✅ O(n \cdot log(n)) représente une complexité linéaire logarithmique, souvent rencontrée dans des algorithmes comme le tri rapide. - [ ] $O(n^2)$ > ❌ O(n^2) représente une complexité quadratique, où le temps d'exécution augmente en fonction du carré de n. # Quel type d’algorithme a une complexité de la forme $O(n^p)$ ? - [ ] Algorithmes logarithmiques > ❌ Les algorithmes logarithmiques ont une complexité de type O(log(n)). - [ ] Algorithmes linéaires > ❌ Les algorithmes linéaires ont une complexité de type O(n). - [x] Algorithmes polynomiaux > ✅ Les algorithmes de type polynomial ont une complexité de la forme O(n^p), où p est une constante. - [ ] Algorithmes exponentiels > ❌ Les algorithmes de type exponentiel ont une complexité de la forme O(p^n), où p est une constante. # Qu’est-ce qui cause le grand nombre de calculs dans un algorithme ? - [x] Le nombre de boucles > ✅ Les boucles augmentent le nombre de calculs en répétant des opérations, ce qui impacte directement la complexité de l'algorithme. - [ ] Le nombre de variables > ❌ Le nombre de variables n'affecte pas directement le nombre de calculs d'un algorithme, sauf si ces variables sont utilisées dans des opérations coûteuses. - [ ] Le nombre de fonctions > ❌ Le nombre de fonctions n'affecte pas le nombre de calculs, bien que certaines fonctions puissent inclure des boucles ou des appels récursifs. # Que doit-on analyser pour avoir la complexité spatiale d’un algorithme ? - [ ] L’espace des données en entrée. > ❌ L’espace des données d’entrée est une partie de la complexité spatiale, mais pas seulement. - [ ] Seule l’espace auxiliaire compte dans le calcul de la mémoire utilisée par l’algorithme > ❌ Il est vrai que l'espace des données en entrée est souvent ignoré car déjà pris en compte dans le problème. Mais selon les cas d'application, la mémoire en entrée joue un rôle crucial dans l'efficacité de l'algorithme. - [ ] L’espace de la pile d’appels > ❌ Les piles d'appels et autres mécanismes algorithmiques demandent de la mémoire et sont donc pris en compte dnas la mémoire auxiliaire. Mais elles ne représentent pas la totalité de la complexité spatiale. - [x] La complexité auxiliaire et celle des données en entrée. > ✅ Effectivement, **complexité spatiale totale = complexité spatiale entrée + complexité spatiale auxiliaire**. # Un algorithme récursif a une profondeur maximale d. Quelle est la contribution de la pile d’appels à la complexité spatiale ? - [ ] $O(1)$. > ❌ Chaque appel garde ses variables sur la pile, donc ce n'est pas constant. - [x] $O(d)$ > ✅ Oui la pile grandit proportionnellement au **nombre d’appels imbriqués**. - [ ] $O(log(d))$ > ❌ $log(d)$ correspondrait à une profondeur exponentiellement plus faible, où le nombre d'appels est divisé par deux. - [ ] $O(n)$ > ❌ Ce serait vrai seulement si la profondeur vaut $n$ (cas linéaire, mais pas général). # Chercher l’existence d’un élément spécifique dans une liste est un exemple de quel type de complexité ? - [ ] Complexité logarithmique > ❌ Une recherche dans une liste non triée nécessite de parcourir chaque élément, ce qui est linéaire, et non logarithmique. - [x] Complexité linéaire > ✅ Une recherche dans une liste non triée a une complexité linéaire O(n) car il faut potentiellement examiner chaque élément. - [ ] Complexité constante > ❌ Une recherche avec complexité constante O(1) n'est possible que dans des structures permettant un accès direct, comme un tableau indexé. - [ ] Complexité quadratique > ❌ La recherche linéaire n'implique pas de double boucle, donc elle n'a pas une complexité quadratique. # Que signifie la notation f(n) = O(g(n)) ? - [x] f(n) croît au plus aussi vite qu’une constante fois g(n) > ✅ À partir d’un certain $n_0$, on a $f(n) \leq c*g(n) pour une constante $c$. - [ ] f(n) croît au moins aussi vite que g(n) > ❌ Ce serait plutôt la définition de $\Omega(g(n)). - [ ] f(n) et g(n) ont la même croissance asymptotique > ❌ Cela correspond à $\Theta(g(n)). # Parmi les fonctions suivantes, laquelle croît le plus vite ? - [ ] $O(n)$ > ❌ C’est linéaire, donc croissance plus lente. - [x] $O(n.log(n))$ > ✅ Oui c'est la complexité quasi-linéaire, donc elle croit plus vite que le linéaire. - [ ] $O(log(n)+ n)$ > ❌ La somme de complexité reste bornée par la fonction qui croit le plus vite. Ici ça reste $O(n)$. - [ ] $O(\sqrt(n)$ > ❌ C'est une complexité croissant moins vite que le linéaire mais plus que le logarithme.