# default_start
def mystere(a):
i = 0
while i < a:
i = i + 2
return i
# default_end
# test_start
print(mystere(5))
# test_endComplexité - Exercices
1 Exercice 1
Difficulté :
Analyser
Quelle est la complexité en temps de la fonction mystere ?
# default_start
def mystere(a):
i = 0 # 1 affectation
# Boucle:
# de i=0 jusqu'à i>=a avec pas de 2
# => (a-0)/2
# => 1/2 * a
# => 0.5a itérations
while i < a: # 1 comparaison
i = i + 2 # 1 affectation + 1 addition
return i # 1 retour
# n = a
# T(n) = 1 + 0.5n * (1 + 2) + 1
# = 1.5n + 2
# => O(n)
# default_endQuelle est la complexité en temps de la fonction mystere ?
# default_start
def mystere(a, b):
ans = None
if a > b:
ans = a * a + b * b
elif a < b:
ans = a + b
else:
ans = 0
return ans
# default_end
# test_start
print(mystere(4,5))
# test_end# default_start
def mystere(a, b):
ans = None # 1 affectation
if a > b: # 1 comparaison
ans = a * a + b * b # 1 affectation + 1 addition + 2 multiplications
elif a < b: # 2 comparaisons (celle du if et celle-ci)
ans = a + b # 1 affectation + 1 addition
else: # 2 comparaisons (celle du if et elif)
ans = 0 # 1 affectation
return ans # 1 retour
# T(n) = 1 + max(1 + 4, 2 + 2, 2 + 1) + 1
# = 1 + 5 + 1
# = 7
# => O(1)
# default_end
# test_start
print(mystere(4,5))
# test_endQuelle est la complexité en temps de la fonction mystere ?
# default_start
def mystere(a):
i = 0
result = 0
while i < 10:
result = result + a
i = i + 1
return result
# default_end
# test_start
print(mystere(5))
# test_end# default_start
def mystere(a):
i = 0 # 1 affectation
result = 0 # 1 affectation
# Boucle:
# i=0 jusqu'à i>=10 avec pas de 1
# => (10 - 0) / 1
# => 10 itérations
while i < 10: # 1 comparaison
result = result + a # 1 affectation + 1 addition
i = i + 1 # 1 affectation + 1 addition
return result # 1 retour
# n = a
# T(n) = 2 + 10(1 + 2 + 2) + 1
# = 53
# => O(1)
# default_end
# test_start
print(mystere(5))
# test_endQuelle est la complexité en temps de la fonction mystere ?
# default_start
def mystere(x):
ans = 0
i = 0
while i < x * x * x:
ans = ans + i
i = i + 1
return ans
# default_end
# test_start
print(mystere(5))
# test_end# default_start
def mystere(x):
ans = 0 # 1 affectation
i = 0 # 1 affectation
# Boucle:
# i=0 jusqu'à i>=x³ avec pas de 1
# => (x³-0)/1
# => x³ itérations
while i < x * x * x: # 1 comparaison + 2 multiplications
ans = ans + i # 1 affectation + 1 addition
i = i + 1 # 1 affectation + 1 addition
return result # 1 retour
# n = x
# T(n) = 2 + n³(3 + 2 + 2) + 1
# = 7n³ + 3
# => O(n³)
# default_end2 Exercice 2
Difficulté :
Analyser
Quelle est la complexité en temps de la fonction mystere ?
# default_start
def mystere(y):
i = 0
if y % 2 == 0:
while i < y:
i = i + 1
else:
while i < 2 ** y:
i = i + 1
return i
# default_end
# test_start
print(mystere(5))
# test_end# default_start
def mystere(y):
i = 0 # 1 affectation
if y % 2 == 0: # 1 modulo + 1 comparaison
# Boucle:
# de i=0 jusqu'à i>=y avec pas de 1
# => (y-0)/1
# => y itérations
while i < y: # 1 comparaison
i = i + 1 # 1 affectation + 1 addition
else: # 1 modulo + 1 comparaison (celle du if)
# Boucle:
# de i=0 jusqu'à i>=2**y avec pas de 1
# => (2**y-0)/1
# => 2**y itérations
while i < 2 ** y: # 1 comparaison + 1 exponentiation
i = i + 1 # 1 affectation + 1 addition
return i # 1 affectation
# n = y
# T(n) = 1 + max(2 + n(1 + 2), 2 + 2**n(2 + 2)) + 1
# = max(3n + 2, 4 * 2**n + 2) + 2
# = 4 * 2**n + 4
# => O(2**n)
# default_endQuelle est la complexité en temps de la fonction mystere ?
# default_start
def mystere(s):
i = 0
res = 0
while i < s:
j = 0
while j < s:
res = res * s
j = j + 1
i = i + 1
return res
# default_end
# test_start
print(mystere(5))
# test_end# default_start
def mystere(s):
i = 0 # 1 affectation
res = 0 # 1 affectation
# Boucle:
# de i=0 jusqu'à i>=s avec pas de 1
# => (s-0)/1
# => s itérations
while i < s: # 1 comparaison
j = 0 # 1 affectation
# Boucle:
# de j=0 jusqu'à j>=s avec pas de 1
# => (s-0)/1
# => s itérations
while j < s: # 1 comparaison
res = res * s # 1 affectation + 1 multiplication
j = j + 1 # 1 affectation + 1 addition
i = i + 1 # 1 affectation + 1 addition
return res # 1 retour
# n = s
# T(n) = 2 + n(2 + n(1 + 2 + 2) + 2) + 1
# = n(5n + 4) + 3
# = 5n² + 4n + 3
# => O(n²)
# default_endQuelle est la complexité en temps de la fonction mystere ?
# default_start
def mystere(s):
i = 0
res = 0
while i < s:
if s < 10:
res = res + 10 * i
elif s < 100:
res = res + 10 * 10 * i
else:
res = res + i
i = i + 1
return res
# default_end
# test_start
print(mystere(5))
# test_end# default_start
def mystere(s):
i = 0 # 1 affectation
res = 0 # 1 affectation
# Boucle:
# de i=0 jusqu'à i>=s avec pas de 1
# => (s-0)/1
# => s itérations
while i < s: # 1 comparaison
if s < 10: # 1 comparaison
res = res + 10 * i # 1 affectation + 1 addition + 1 multiplication
elif s < 100: # 2 comparaisons (celle du if et celle-ci)
res = res + 10 * 10 * i # 1 affectation + 1 addition + 2 multiplications
else: # 2 comparaisons (celle du if et du elif)
res = res + i # 1 affectation + 1 addition
i = i + 1 # 1 affectation + 1 addition
return res # 1 retour
# n = s
# T(n) = 2 + n(1 + max(1 + 3, 2 + 4, 2 + 2) + 2 + 1) + 1
# = n(max(4, 6, 4) + 4) + 3
# = 10n + 3
# => O(n)
# default_endQuelle est la complexité en temps de la fonction mystere ?
# default_start
def mystere(k):
i = 0
res = 0
while i < 3:
j = 0
while j < 3 * k:
res = res * k + 3
j = j + 1
i = i + 1
return res
# default_end
# test_start
print(mystere(5))
# test_end# default_start
def mystere(k):
i = 0 # 1 affectation
res = 0 # 1 affectation
# Boucle:
# de i=0 jusqu'à i>=3 avec pas de 1
# => (3-0)/1
# => 3 itérations
while i < 3: # 1 comparaison
j = 0 # 1 affectation
# Boucle:
# de j=0 jusqu'à j>=3k avec pas de 1
# => (3k-0)/1
# => 3k itérations
while j < 3 * k: # 1 comparaison + 1 multiplication
res = res * k + 3 # 1 affectation + 1 multiplication + 1 addition
j = j + 1 # 1 affectation + 1 addition
i = i + 1 # 1 affectation + 1 addition
return res # 1 retour
# n = k
# T(n) = 1 + 1 + 3(1 + 1 + 3n(2 + 3 + 2) + 2) + 1
# = 3(21n + 4) + 3
# = 63n + 15
# => O(n)
# default_end3 Exercice 3
Difficulté :
Analyser
Quelle est la complexité en temps de la fonction mystere ?
# default_start
def mystere(t):
i = 0
ans = 1
while i < t:
ans = 2 * ans
i = i + 1
i = 0
result = 0
while i < ans:
result = result + ans
i = i + 1
return result
# default_end
# test_start
print(mystere(5))
# test_end# default_start
def mystere(t):
i = 0 # 1 affectation
ans = 1 # 1 affectation
# Boucle:
# de i=0 jusqu'à i>=t avec pas de 1
# => (t - 0) / 1
# => t itérations
while i < t: # 1 comparaison
ans = 2 * ans # 1 affection + 1 multiplication
i = i + 1 # 1 affectation + 1 multiplication
i = 0 # 1 affectation
result = 0 # 1 affectation
# Boucle:
# de i=0 jusqu'à i>=ans avec pas de 1
# => (ans - 0)/ 1
# => ans itérations
# Problème:
# Que vaut ans en fonction des données d'entrée (t) ?
# Réponse:
# t=0 ans = 1 => 1 iteration
# t=1 ans = 2 *(1) => 2 iterations
# t=2 ans = 2 * (2 *(1)) => 4 iterations
# t=2 ans = 2 * (2 * (2 *(1))) => 8 iterations
# t=3 ans = 2 * (2 * (2 * (2 *(1)))) => 16 iterations
# ...
# => 2^t (exponentielle base 2) itérations
while i < ans: # 1 comparaison
result = result + ans # 1 affectation + 1 division
i = i + 1 # 1 affectation + 1 addition
return result # 1 retour
# n = t
# T(n) = 2 + n(1 + 2 + 2) + 1 + 1 + 2^n(1 + 2 + 2) + 1
# = 5 * 2**n + 5n + 5
# => O(2**n)
# default_endQuelle est la complexité en temps de la fonction mystere ?
# default_start
def mystere(n):
f = 1
i = 1
while i < n + 1:
f = f * i
i = i + 1
i = 0
res = 0
while i < f:
res = res + i
i = i + 1
return res
# default_end
# test_start
print(mystere(5))
# test_end# default_start
def mystere(n):
f = 1 # 1 affectation
i = 1 # 1 affectation
# de i=1 jusqu'à i>=n+1 avec pas de 1 => (n+1-1)/1 => n itérations
# Boucle:
# de i=1 jusqu'à i>=n+1 avec pas de 1
# => (n+1 - 1) / 1
# => n itérations
while i < n + 1: # 1 comparaison + 1 addition
f = f * i # 1 affectation + 1 multiplication
i = i + 1 # 1 affectation + 1 addition
i = 0 # 1 affectation
res = 0 # 1 affectation
# Boucle:
# de i=0 jusqu'à i>=f avec pas de 1
# => (f - 0) / 1
# => f itérations
# Problème :
# que vaut f en fonction des données d'entrée (n) ?
# Réponse :
# n=0 f = 1 = 1 itération
# n=1 f = (1) * 1 = 1 itérations
# n=2 f = ((1) * 1) * 2 = 2 itérations
# n=3 f = (((1) * 1) * 2) * 3 = 6 itérations
# n=4 f = ((((1) * 1) * 2) * 3) * 4 = 24 itérations
# n=5 f = (((((1) * 1) * 2) * 3) * 4) * 5 = 120 itérations
# ...
# soit n! (factorielle)
while i < f: # 1 comparison
res = res + i # 1 affectation + 1 addition
i = i + 1 # 1 affectation + 1 addition
return res # 1 retour
# n = n
# T(n) = 2 + n(2 + 2 + 2) + 2 + n!(1 + 2 + 2) + 1
# = 5n! + 6n + 5
# = O(n!)
# default_end4 Exercice 4
Difficulté :
Quelle est la complexité en temps de la fonction mystere ?
# default_start
def mystere(a):
res = 0
i = a
while i > 1:
res = res + a
i = i // 2
return res
# default_end
# test_start
print(mystere(15))
# test_end# default_start
def mystere(a):
res = 0 # 1 affectation
i = a # 1 affectation
# Boucle:
# de i=a jusqu'à i<=1 avec i//2 à chaque itération.
# On ne peut pas faire (point d'arrivée - point de départ) / pas car
# i//2 n'est pas un pas constant donc il faut raisonner autrement...
# Problème:
# que vaut i en fonction des données d'entrée (a) ?
# Réponse:
# a=15 i=15, i=7, i=3, i=1 => 4 itérations
# a=14 i=14, i=7, i=3, i=1 => 4 itérations
# a=13 i=13, i=6, i=3, i=1 => 4 itérations
# a=12 i=12, i=6, i=3, i=1 => 4 itérations
# a=11 i=11, i=5, i=2, i=1 => 4 itérations
# a=10 i=10, i=5, i=2, i=1 => 4 itérations
# a=9 i=9, i=4, i=2, i=1 => 4 itérations
# a=8 i=8, i=4, i=2, i=1 => 4 itérations
# a=7 i=7, i=3, i=1 => 3 itérations
# a=6 i=6, i=3, i=1 => 3 itérations
# a=5 i=5, i=2, i=1 => 3 itérations
# a=4 i=4, i=2, i=1 => 3 itérations
# a=3 i=3, i=1 => 2 itérations
# a=2 i=2, i=1 => 2 itérations
# a=1 i=1, i=1 => 1 itérations
# ...
# soit log2(a) + 1
while i > 1: # 1 comparaison
res = res + a # 1 affectation + 1 addition
i = i // 2 # 1 affectation + 1 division entière
return res # 1 retour
# n = a
# T(n) = 1 + 1 + (log2(n) + 1) * 5 + 1
# = 5(log2(n) + 1) + 3
# = 5log2(n) + 8
# => O(log(n))
# Astuce à retenir:
# si on divise par 2 à chaque itération, le nombre d'itérations est au minimum log2(n).
# default_end# default_start
print("Hello World!")
# default_end