Aller au contenu

QCM
Complexité

Rappel

Les questions ci-dessous sont là pour vous aider à contrôler ce que vous avez retenu.
Si vous ne répondez pas à toutes les questions sans hésitation, c'est sans doute qu'il faut retravailler les pages précédentes.

Pour chaque question, il faut trouver la (ou les) bonne(s) réponse(s).

QCM 1

On considère l'algorithme suivant :

1
2
3
4
Pour i allant de 1 à n:
    Pour j allant de 1 à n:
        Pour k allant de 1 à n:
            actions à temps constant (opérations élémentaires)

Le nombre d'opérations est plutôt de l'ordre de :

  • n
  • n²
  • n³
  • n
Réponse
  • n
  • n²
  • n³ (complexité cubique)
  • n

QCM 2

On considère la fonction suivants, définie en Python :
Cette fonction n'a aucun intérêt ; il est inutile de chercher à comprendre son rôle.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def f(n):
    """
    n - int, entier positif
    """
    m = 10
    k = 0
    for i in range(n):
        for j in range(m):
            k = k+1      
    return k

Le type de complexité est plutôt :

  • constante en O(1)
  • linéaire en O(n)
  • quadratique en O(n²)
  • cubique en O(n³)
Réponse
  • constante en O(1)
  • linéaire en O(n)
  • quadratique en O(n²)
  • cubique en O(n³)

En effet, la boucle interne fait un nombre d'itérations constants (car m est constant). Cette boucle

5
6
for j in range(m):
    k = k+1
pourrait être remplacée par dix instructions d'affectations.

En d'autres termes, le nombre d'exécutions de la ligne 6 est 10n.

QCM 3

On considère la fonction suivants, définie en Python :
Cette fonction n'a aucun intérêt ; il est inutile de chercher à comprendre son rôle.

1
2
3
4
5
6
7
8
def f(n):
    """
    n - int, entier positif
    """
    x = 0
    while x*x < n:
        x = x+1
    return x

Le nombre d'opération est plutôt de l'ordre de :

  • \sqrt{n}
  • n
  • n^2
  • x
Réponse
  • \sqrt{n}
  • n
  • n^2
  • x

On peut réécrire la fonction f ainsi:

1
2
3
4
5
6
7
8
9
from math import sqrt
def f(n):
    """
    n - int, entier positif
    """
    x = 0
    while x < sqrt(n):
        x = x+1
    return x