Avancé
🧠 Fondamentaux
30 XP
0 personnes ont réussi
Comparer les complexités
Pour bien comprendre les differences de complexité, rien de mieux que de les implémenter cote a cote.
O(1) veut dire temps constant : peu importe la taille des données, ca prend toujours le meme temps. Acceder au premier élément d'une liste, c'est O(1).
O(n) veut dire temps lineaire : tu parcours les éléments un par un. Chercher un élément dans une liste non triee, c'est O(n).
O(n²) veut dire temps quadratique : pour chaque élément, tu regardes tous les autres. Vérifier s'il y a des doublons avec deux boucles, c'est O(n²).
Écris trois fonctions :
1. f_constante(lst) qui retourne le premier élément de la liste, ou None si elle est vide. C'est O(1).
2. f_lineaire(lst, val) qui retourne True si val est dans lst, False sinon. C'est O(n).
3. f_quadratique(lst) qui retourne True si la liste contient des doublons, False sinon. Utilise deux boucles imbriquees, sans utiliser set.
def f_constante(lst):
if not lst:
return None
return lst[0]
def f_lineaire(lst, val):
for x in lst:
if x == val:
return True
return False
def f_quadratique(lst):
for i in range(len(lst)):
for j in range(i + 1, len(lst)):
if lst[i] == lst[j]:
return True
return False