Notions de base en algo (Complexité temporelle)

Question 1

Qu’est-ce que la complexité temporelle ?

Answer 1

Une mesure du temps d’exécution d’un algorithme en fonction de la taille des données d’entrée (n), exprimée avec la notation O.

Question 2

Que représente la notation O ?

Answer 2

Le comportement asymptotique (pire cas) d’un algorithme, en ignorant les constantes et les termes non dominants.

Question 3

Comment simplifier O(3n² + 2n + 5) ?

Answer 3

O(n²) (on garde le terme dominant).

Question 4

Quelle est la complexité d’une boucle for i in range(n) ?

Answer 4

O(n).

Question 5

Et de deux boucles imbriquées ?

Answer 5

O(n²).

Question 6

Pourquoi la recherche dichotomique est-elle O(log n) ?

Answer 6

Parce qu’elle divise l’espace de recherche par 2 à chaque étape (log₂n étapes max).

Question 7

Quel est l’accès à un élément dans un tableau ? Et dans une liste chaînée ?

Answer 7

Tableau : O(1) (accès direct).

Liste chaînée : O(n) (parcours nécessaire).

Question 8

Pourquoi s += str(i) dans une boucle peut être O(n²) ?

Answer 8

Parce que les strings sont immuables (chaque concaténation crée une nouvelle string, coût total cumulé).

Question 9

Quelle est la complexité de Fibonacci naïf ? Et avec mémoïsation ?

Answer 9

Naïf : O(2ⁿ) (branchement exponentiel).

Mémoïsation : O(n) (calculs stockés).

Question 10

Que devient O(n + log n) après simplification ?

Answer 10

O(n) (car n domine log n).

Question 11

Pourquoi for x in list: list.remove(x) est O(n²) ?

Answer 11

Car remove() est O(n) et est appelé n fois.

Question 12

Complexité du tri fusion ? Et du tri par sélection ?

Answer 12

Tri fusion : O(n log n).

Tri par sélection : O(n²).

Question 13

Quelle est la complexité d’un parcours DFS sur un graphe ?

Answer 13

O(n + m) (où n = nœuds, m = arêtes).

Question 14

Comment analyser la complexité d’un algorithme ?

Answer 14

Compter les opérations dominantes (boucles, récursions).

Tenir compte des structures de données.

Simplifier en notation O.

Question 15

Complexité des opérations suivantes sur un tableau ?

Accès (arr[i])

Recherche d'un élément

Insertion/suppression en fin (append(), pop())

Insertion/suppression au milieu

Answer 15

Accès : O(1)

Recherche (non trié) : O(n)

Fin : O(1) (amorti)

Milieu : O(n) (décalage des éléments)

Question 16

Complexité des opérations suivantes ?

Insertion en tête

Recherche d'un élément

Accès au i-ème élément

Answer 16

Tête : O(1)

Recherche/Accès : O(n) (parcours nécessaire)

Question 17

Complexité des opérations ?

Insertion (dict[key] = value)

Recherche (key in dict)

Suppression (del dict[key])

Answer 17

En moyenne : O(1)

Pire cas (collisions) : O(n)

Question 18

Complexité de push()/pop() (pile) et enqueue()/dequeue() (file) ?

Answer 18

Toutes : O(1) (implémentation standard avec liste ou deque)

Question 19

Complexité des opérations suivantes sur les arbres binaires équilibrés ?

Recherche

Insertion

Suppression

Answer 19

Toutes : O(log n) (hauteur de l’arbre = log n)

Question 20

Complexité de insert() et extract_min() sur un tas (heap) ?

Answer 20

Les deux : O(log n) (rééquilibrage après opération)

Question 21

Complexité dans le pire cas ? Et en moyenne ? (Tri Rapide /QuickSort)

Answer 21

Pire cas : O(n²) (mauvais pivot)

Moyenne : O(n log n)

Question 22

Complexité dans tous les cas pour le Tri Fusion (MergeSort)?

Answer 22

Toujours : O(n log n) (stable et diviser-pour-régner)

Question 23

Complexité pour un graphe avec n nœuds et m arêtes ? (BFS ou DFS)

Answer 23

BFS/DFS : O(n + m) (visite chaque nœud et arête une fois)

Question 24

Complexité avec un tas binaire ? Et avec un tas de Fibonacci ?

Answer 24

Tas binaire : O((n + m) log n)

Tas de Fibonacci : O(n log n + m)

Question 25

Pourquoi s += "a" dans une boucle est O(n²) ?

Answer 25

Strings immuables → copie complète à chaque itération ("a" + "b" + ...). Solution : Utiliser "".join(list) pour O(n).

Question 26

Complexité de list[start:end] ?

Answer 26

O(k) (où k = end - start) → copie des éléments.

Question 27

Complexité de : python for x in list: if x in other_list: # other_list de taille m print(x)

Answer 27

O(n × m) (boucle O(n) × recherche O(m)).

Question 28

Complexité avec l'opération Union-Find optimisée pour l'algo de kruskal?

Answer 28

O(m log n) (où m = arêtes, n = nœuds).

Question 29

Qu’est-ce que la complexité temporelle en cas moyen ?

Answer 29

Le temps d’exécution moyen attendu pour des données aléatoires, calculé en probabilités.

Question 30

Qu’est-ce que la complexité temporelle en meilleur cas ?

Answer 30

Le temps d’exécution minimal possible (scénario idéal, souvent peu réaliste).

Question 31

Quelle est la complexité de QuickSort en cas moyen ? Pourquoi ?

Answer 31

O(n log n). Le pivot divise le tableau en parties équilibrées en moyenne.

Question 32

Donnez un exemple de meilleur cas O(1).

Answer 32

Recherche linéaire où la cible est en première position.

Question 33

Comment calculer le cas moyen pour un tri ?

Answer 33

Moyenner le nombre de comparaisons sur toutes les permutations possibles des données.

Question 34

Pourquoi le meilleur cas est rarement utilisé ?

Answer 34

Car il est souvent irréaliste (ex: tableau déjà trié pour le tri par insertion).

Question 35

Donnez un exemple d’algo où cas moyen = pire cas.

Answer 35

Tri Fusion → O(n log n) dans tous les cas (stable et déterministe).

Question 36

Quand utilise-t-on le cas moyen en pratique ?

Answer 36

Pour les applications grand public où les données sont imprévisibles mais pas malveillantes.