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 :

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.

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

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.

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:

from math import sqrt
def f(n):
    """
    n - int, entier positif
    """
    x = 0
    while x < sqrt(n):
        x = x+1
    return x