Testez vos connaissances en complexité algorithmique — Terminale Informatique

Question 1 sur 10 10:00

[{"id":57261,"question":"Quelle notation asymptotique représente le pire cas de complexité temporelle d'un algorithme ?","option_a":"O(1)","option_b":"O(n)","option_c":"O(n²)","option_d":"Ω(n)","option_e":"","option_f":"","bonne_reponse":"C","explication":"La notation Ω(n) représente le pire cas de complexité temporelle, indiquant que l'algorithme prendra au moins ce temps pour s'exécuter. Les autres notations (O) représentent des cas limites supérieurs ou des complexités spécifiques.","points":1,"type":"qcm","actif":1,"section_id":null,"ordre":0},{"id":57262,"question":"Un algorithme de tri a une complexité de O(n log n). Que signifie cette notation ?","option_a":"Vrai","option_b":"Faux","option_c":"","option_d":"","option_e":"","option_f":"","bonne_reponse":"A","explication":"Vrai. La notation O(n log n) signifie que le temps d'exécution de l'algorithme croît proportionnellement à n multiplié par le logarithme de n. C'est une complexité courante pour les algorithmes de tri efficaces comme le tri fusion ou le tri rapide.","points":1,"type":"qcm","actif":1,"section_id":null,"ordre":0},{"id":57263,"question":"Quel est le résultat de la complexité asymptotique de l'algorithme suivant : pour i de 1 à n faire pour j de 1 à n faire instruction end end ?","option_a":"O(n)","option_b":"O(n²)","option_c":"O(2^n)","option_d":"O(log n)","option_e":"","option_f":"","bonne_reponse":"B","explication":"La complexité est O(n²) car il y a deux boucles imbriquées, chacune s'exécutant n fois. Le nombre total d'instructions est donc proportionnel à n multiplié par n, soit n².","points":1,"type":"qcm","actif":1,"section_id":null,"ordre":0},{"id":57264,"question":"La complexité spatiale d'un algorithme est toujours inférieure ou égale à sa complexité temporelle.","option_a":"Vrai","option_b":"Faux","option_c":"","option_d":"","option_e":"","option_f":"","bonne_reponse":"B","explication":"Faux. La complexité spatiale (mémoire utilisée) et la complexité temporelle (temps d'exécution) sont indépendantes. Un algorithme peut avoir une faible complexité temporelle mais une forte complexité spatiale, et vice versa.","points":1,"type":"qcm","actif":1,"section_id":null,"ordre":0},{"id":57265,"question":"Quel algorithme a une complexité temporelle de O(log n) ?","option_a":"Recherche linéaire","option_b":"Tri à bulles","option_c":"Recherche dichotomique","option_d":"Tri par insertion","option_e":"","option_f":"","bonne_reponse":"C","explication":"La recherche dichotomique a une complexité de O(log n) car elle divise l'espace de recherche par deux à chaque étape, réduisant ainsi le nombre d'opérations nécessaires.","points":1,"type":"qcm","actif":1,"section_id":null,"ordre":0},{"id":57266,"question":"Si un algorithme a une complexité de Θ(n²), quelle affirmation est correcte ?","option_a":"Son temps d'exécution est toujours inférieur à n²","option_b":"Son temps d'exécution est exactement n²","option_c":"Son temps d'exécution est proportionnel à n²","option_d":"Son temps d'exécution est indépendant de n","option_e":"","option_f":"","bonne_reponse":"C","explication":"La notation Θ(n²) signifie que le temps d'exécution de l'algorithme est proportionnel à n², ni plus ni moins. Cela indique une croissance quadratique du temps d'exécution.","points":1,"type":"qcm","actif":1,"section_id":null,"ordre":0},{"id":57267,"question":"Un algorithme de recherche dans un tableau trié a une complexité de O(n). Que peut-on en déduire ?","option_a":"Vrai","option_b":"Faux","option_c":"","option_d":"","option_e":"","option_f":"","bonne_reponse":"A","explication":"Vrai. Une complexité de O(n) pour une recherche dans un tableau trié suggère que l'algorithme utilisé est probablement une recherche linéaire, qui parcourt chaque élément un par un. Une recherche dichotomique serait plus efficace avec O(log n).","points":1,"type":"qcm","actif":1,"section_id":null,"ordre":0},{"id":57268,"question":"Quelle est la complexité asymptotique de l'algorithme suivant : pour i de 1 à n faire instruction end pour j de 1 à n faire instruction end end ?","option_a":"O(n)","option_b":"O(n²)","option_c":"O(2n)","option_d":"O(n + n)","option_e":"","option_f":"","bonne_reponse":"A","explication":"La complexité est O(n) car les deux boucles sont séquentielles et non imbriquées. Le nombre total d'instructions est proportionnel à n + n, soit 2n, mais en notation asymptotique, on simplifie en O(n).","points":1,"type":"qcm","actif":1,"section_id":null,"ordre":0},{"id":57269,"question":"La notation O(1) signifie que l'algorithme s'exécute en temps constant, quel que soit n.","option_a":"Vrai","option_b":"Faux","option_c":"","option_d":"","option_e":"","option_f":"","bonne_reponse":"A","explication":"Vrai. La notation O(1) indique que le temps d'exécution de l'algorithme ne dépend pas de la taille des données d'entrée. Il reste constant, même si n augmente.","points":1,"type":"qcm","actif":1,"section_id":null,"ordre":0},{"id":57270,"question":"Quel algorithme parmi les suivants a une complexité temporelle de O(n log n) ?","option_a":"Tri par sélection","option_b":"Tri à bulles","option_c":"Tri fusion","option_d":"Tri par insertion","option_e":"","option_f":"","bonne_reponse":"C","explication":"Le tri fusion a une complexité de O(n log n), car il divise le tableau en sous-tableaux plus petits, les trie récursivement, puis les fusionne. C'est l'un des algorithmes de tri les plus efficaces.","points":1,"type":"qcm","actif":1,"section_id":null,"ordre":0}]