Complexité O(n) — somme d'une liste

Quand on parle de complexité algorithmique, on cherche a savoir comment le temps d'execution evolue quand la taille des données augmente.

O(n), ca veut dire lineaire : si ta liste double de taille, le temps double aussi. C'est le cas quand tu parcours une liste élément par élément, une seule fois.

Par exemple, pour calculer la somme d'une liste de 5 éléments, tu fais 5 additions. Pour 10 éléments, tu en fais 10. C'est proportionnel.

Écris une fonction somme_lineaire(lst) qui retourne la somme de tous les éléments d'une liste en parcourant chaque élément une seule fois.

Exemple :
somme_lineaire([1, 2, 3, 4, 5]) renvoie 15
somme_lineaire([]) renvoie 0

Tests (3/4)

Liste simple

assert somme_lineaire([1, 2, 3, 4, 5]) == 15

Liste vide

assert somme_lineaire([]) == 0

Un élément

assert somme_lineaire([42]) == 42

+ 0 tests cachés

Indices (3 disponibles)

Solution officielle

def somme_lineaire(lst):
    total = 0
    for x in lst:
        total += x
    return total

Complexité O(n²) — paires en … →

solution.py

Bravo!

Complexité O(n) — somme d'une liste

Tests (3/4)

Indices (3 disponibles)

Solution officielle