Lire des coûts

Exercice · informatique (tronc commun des prépas scientifiques), chapitre 2 — Recherche séquentielle et dictionnaires

Énoncé

Déterminer la complexité dans le cas le pire (en fonction de $n = len (t)$ ) des trois codes suivants :

# (a)
x = t[0] + t[-1]

# (b)
s = 0
for x in t:
    if x > 0:
        s += x

# (c)
p = 0
for x in t:
    if x in t:
        p += 1

(a) : Le code effectue deux accès à la liste et une addition. Le coût est constant, soit $O (1)$ .
(b) : La boucle s'exécute $n$ fois. Chaque étape effectue des opérations élémentaires en $O (1)$ (comparaison, addition). La complexité est linéaire, soit $O (n)$ .
(c) : La boucle externe s'exécute $n$ fois. À chaque itération, le test x in t effectue un parcours complet de la liste, ce qui coûte $O (n)$ dans le cas le pire. La complexité globale est donc quadratique, soit $O (n^{2})$ .

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.