Crowdly
Add to Chrome
[25-26] Algorithmique avancée 2 [S3] [SPE]
Looking for [25-26] Algorithmique avancée 2 [S3] [SPE] test answers and solutions? Browse our comprehensive collection of verified answers for [25-26] Algorithmique avancée 2 [S3] [SPE] at moodle.esme.fr.
Get instant access to accurate answers and detailed explanations for your course questions. Our community-driven platform helps students succeed!
Considérons l’algorithme suivant :
def algorithm_D(m, n): i =
1 j =
1
while (j <= n):
if i <= m:
i = i +
1
else:
j = j +
1 i =
1Quelle est la complexité temporelle de cet algorithme, sachant que n et m sont strictement positif ?
Considérons la fonction suivante :
def example_function(n): total =
0
for i in range(n):
total += i
for i in range(n):
for j in range(n):
total += i * j
for i in range(n):
for j in range(n):
for k in range(n):
total += i * j * k
return total
Quelle est la complexité temporelle de cette fonction ?
Considérons l’algorithme suivant (tri par insertion) :
def tri(array): n = len(array)
for i in range(1, n):
key = array[i]
j = i -
1
while j >= 0 and array[j] > key:
array[j +
1] = array[j]
j = j -
1 array[j +
1] = key
print(array)
return array
Quelle est la complexité temporelle
dans le pire cas ?Considérons l’algorithme suivant pour calculer x^n :
def puissance_rapide(x, n):
if n == 0:
return 1
elif n % 2 == 0:
p = puissance_rapide(x, n/
2)
return p * p
else:
p = puissance_rapide(x, (n
-1)/2)
return x * p * p
Quelle est la complexité temporelle de cette fonction ?
Considérons la fonction récursive suivante :
def uk(n, acc=1):
if n == 0:
return acc
else:
return uk(n-1, 4*acc)
Quelle est la complexité temporelle de cette fonction ?
Considérons la fonction suivante :
def fib_naif(n):
if n <= 1:
return n
return fib_naif(n-1) + fib_naif(n-2)
Quelle est la complexité temporelle de cette fonction ?
Considérons le parcours infixe d'un arbre binaire :
def parcours_infixe(node):
if node:
parcours_infixe(node.left)
print(node.val)
parcours_infixe(node.right)
Quelle est la complexité temporelle ?
Considérons l’algorithme de recherche dichotomique (binaire) dans un tableau trié :
def binary_search_recursive(arr, x, low=0, high=None):
if high is None:
high = len(arr) -
1
if low > high:
return -1 mid = (low + high) //
2
if arr[mid] == x:
return mid
elif arr[mid] < x:
return binary_search_recursive(arr, x, mid + 1, high)
else:
return binary_search_recursive(arr, x, low, mid - 1)Quelle est sa complexité temporelle dans le **pire cas** ?Considérons l’algorithme de tri fusion suivant :
def merge_sort(array):
if len(array) <= 1:
return array
middle = len(array) //
2 left = merge_sort(array[:middle])
right = merge_sort(array[middle:])
return merge(left, right)Quelle est sa complexité temporelle dans le **pire cas** ?
Consider the following function:
def example_function(n):
total =
0
for i in range(n):
total += i
for i in range(n):
for j in range(n):
total += i * j
for i in range(n):
for j in range(n):
for k in range(n):
total += i * j * k
return total
What is the time complexity of this function?