QCM☘

On considère le code suivant:

def f(n):
    """
    n -- entier naturel
    """
    x = 1
    while x < n:
        x = 2*x
    return x

On s'intéresse au coût en termes de nombre d'opérations en fonction de l'entrée n.

Ce coût est similaire à celui d'une recherche dichotomique sur une liste de taille n.
Ce coût est linéaire en n (≈ fonction affine de la variable n)
Ce coût est quadratique en n (≈ fonction du second degré de la variable n)
Ce coût est de l'ordre de √n.

Réponse

Ce coût est similaire à celui d'une recherche dichotomique sur une liste de taille n.
Ce coût est linéaire en n (≈ fonction affine de la variable n)
Ce coût est quadratique en n (≈ fonction du second degré de la variable n)
Ce coût est de l'ordre de √n.

On pourrait réécrire le code comme suit:

def g(n):
    """
    n -- entier naturel
    """
    x = 1
    m = n
    while 1 < m:
        x = 2*x
        m = m/2
    return x

On divise par 2 la "taille" du problème, comme pour une recherche dichotomique.

Rappelons que l'on peut encadrer l'entier n par deux puissances de 2 successives: $2^k \leqslant n < 2^{k+1}$ . C'est ce nombre $k$ qui donne l'ordre de grandeur du nombre d'opérations (on parle de logarithme entier à base 2 de l'entier n).

QCM☘

On a effectué une recherche dichotomique dans une liste (triée) de taille n (n > 100000). Cela demande k exécutions du corps de la boucle de l'algorithme de recherche dans le pire des cas.

Pour une liste de taille 2n, le pire cas demande un nombre d'exécutions du corps de la boucle de l'algorithme de recherche de l'ordre de:

k
2k
k²

Réponse

k
2k
k²

Dans le principe de dichotomie, on divise par 2 la taille de liste à chaque étape. Avec une liste de taille 2n, en une étape on est ramené à une liste de taille n. Par rapport à une liste de taille n, il n'y a donc qu'une seule étape en plus pour une liste de taille 2n. Le nombre de passages dans la boucle est donc k+1 au pire cas.
Multiplier par deux la taille de la liste dans laquelle cherchée n'augmente donc quasiment pas le temps de recherche (une seule étape ajoutée).

QCM☘

Avec un algorithme de recherche dichotomique, combien d'étapes sont nécessaires pour déterminer que 35 est présent dans le tableau [1, 7, 12, 16, 18, 20, 24, 28, 35, 43, 69]?

1
2
9
11

Réponse

1
2
9
11

QCM☘

Pour pouvoir utiliser un algorithme de recherche par dichotomie dans une liste, quelle précondition doit être vraie?

La liste ne doit pas comporter de doublons.
La liste doit comporter uniquement des entiers positifs.
La liste doit être triée.
La longueur de la liste doit être une puissance de 2.

Réponse

La liste ne doit pas comporter de doublons.
La liste doit comporter uniquement des entiers positifs.
La liste doit être triée.
La longueur de la liste doit être une puissance de 2.

QCM☘

Existe-t-il des instances du problème de recherche d'un élément dans un tableau pour lesquelles la recherche séquentielle (présentée en page index) est plus rapide qu'une recherche par dichotomie?

Oui
Non

Réponse

Oui
Non

Si la liste est [3, 8, 9, 42, 666, 1789, 1968] et que l'on cherche 3, une recherche séquentielle trouve en une étape le nombre, alors que la recherche dichotomique nécessitera plusieurs étapes.