COMPLX

Quel est le temps d'exécution moyen d'une recherche dans une table de hachage bien conçue avec gestion efficace des collisions ?

• O(n)

• o(log n)

• o(1)

• o(n²)

La complexité temporelle de l'algorithme de tri rapide (QuickSort) dans le pire cas est :

• o(n log n)

• o(n²)

• o(log n)

• o(1)

Quelle structure de données permet d'effectuer des recherches, insertions et suppressions en O(log⁡n) dans le pire des cas ?

• Tableau trié

• Liste chaînée

• Tas binaire (Binary Heap)

• Arbre de recherche équilibré

Quelle est la complexité amortie d'une opération "push" sur une pile extensible implémentée par un tableau dynamique ?

• o(1)

• o( n)

• o(log n)

• o( n² )

La notation O(f(n)) signifie

• Une complexité au pire cas égale à f(n)

• Une complexité inférieure à f(n)

• Une complexité asymptotiquement bornée supérieure par f(n)

• Une complexité asymptotiquement bornée supérieure ou égale par f(n)

Si un problème appartient à la classe NP et que vous trouvez une solution en temps polynomial, alors :

• P ≠ NP

• NP ⊂ P

• P = NP

• Aucune des réponses

Si 𝑓(𝑛) ∈ O(𝑔(𝑛)), 𝑎𝑙𝑜𝑟𝑠 𝑔(𝑛) ∈

O(𝑓(𝑛)).

• vrai

• faux

Si 𝑓(𝑛) ∈ O(𝑔(𝑛)), 𝑎𝑙𝑜𝑟𝑠 𝑓(𝑛) +

𝑔(𝑛) ∈ O(𝑔(𝑛))

• Vrai

• Faux

La meilleure borne asymptotique de

𝑂(𝑓(n)) + 𝑂(𝑔(n)) est 𝑂(𝑓(n) + 𝑔(n))

• Vrai

• Faux

Si 𝑔 = 𝑂(𝑓(n)) et ℎ = 𝑂(𝑔(n)) alors ℎ

= 𝑂(𝑓(n))

• Vrai

• Faux