7. Analyse du Temps Linéaire : O(N)

Un algorithme s'exécute en Temps Linéaire, O(N), si le temps d'exécution augmente directement et proportionnellement avec la taille de l'entrée (N).

Si l'entrée double, le temps d'exécution double approximativement.

Exemple : Itération Simple (Recherche dans un tableau)

Si vous voulez trouver un élément dans une liste (sans connaître sa position), dans le pire des cas, vous pourriez devoir regarder chaque élément.

python def find_item(data, target): # The loop runs N times, where N is the length of 'data' for item in data: if item == target: return True return False

Si N=100, la boucle s'exécute 100 fois. Si N=1000, elle s'exécute 1000 fois. Cette relation directe en fait O(N).