Complexité

Questions

Complexité

1. Quel est l'ordre de grandeur de la complexité d'un algorithme qui effectue une boucle sur une liste de taille \(n\) puis une fois que la première boucle est terminée, une seconde boucle sur une liste de taille \(n\) ?
   • constante

   • logarithmique

   • linéaire

   • quadratique

2. On considère un programme dont le temps d'exécution augmente d'une unité à chaque fois que la taille \(n\) de l'entrée est multipliée par 2. L'ordre de grandeur de sa complexité est :
   • logarithmique

   • linéaire

   • quadratique

   • exponentielle

3. On considère un programme dont le temps d'exécution est multiplié par 8 à chaque fois que la taille \(n\) de l'entrée est multipliée par 2. L'ordre de grandeur de sa complexité est :
   • linéaire

   • quadratique

   • cubique

   • exponentielle

4. On considère un programme dont le temps d'exécution est multipliée par 4 à chaque fois que la taille \(n\) de l'entrée est multipliée par 2. L'ordre de grandeur de sa complexité est :
   • linéaire

   • quadratique

   • cubique

   • exponentielle

5. On considère un programme dont le temps d'exécution est multiplié par 2 à chaque fois que la taille \(n\) de l'entrée augmente de 1. L'ordre de grandeur de sa complexité est :
   • linéaire

   • quadratique

   • cubique

   • exponentielle

6. On considère la fonction suivante :
   Python

   def f(n):
      while n > 0:
         print("*")
         n = n // 2
   

   Quel est l'ordre de grandeur de la complexité de cette fonction ?

   • logarithmique

   • linéaire

   • quadratique

   • exponentielle

7. Le nombre de comparaisons pour un tri par sélection dans l'ordre croissant d'une liste de \(n\) entiers est :
   • linéaire de l'ordre de \(n\)

   • dépend de la liste donné en entrée

   • quadratique de l'ordre de \(n^{2}\)

   • cubique de l'ordre de \(n^{3}\)

8. Le nombre de comparaisons pour un tri par insertion dans l'ordre croissant d'une liste de \(n\) entiers déjà triée est :
   • linéaire, de l'ordre de \(n\)

   • dépend de la liste donné en entrée

   • quadratique de l'ordre de \(n^{2}\)

   • cubique de l'ordre de \(n^{3}\)