def foo(n):
def bar(n):
if n == 0:
return 0
else:
return 1 + bar (n - 1)
return n * bar(n)
Comment calculer la complexité temporelle de la durée de fonctionnement de foo en fonction de son entrée n? Qu'en est-il de la complexité spatiale?Détermination de la complexité temporelle et spatiale d'une fonction récursive
Brisons-le:
return n * bar(n)
→ n * (1 + bar(n - 1))
→ n * (1 + 1 + bar(n - 2))
→ n * (1 + 1 + 1 + bar(n - 3))
→ n * (1 + 1 + 1 + .... <n times> + bar(0))
→ n * n
Cela semble linéaire dans le temps et la mémoire - O(n).
pourquoi n'est-il pas comme pour bar(), le n des étapes est n + 1, et pour foo() il est n (n + 1), donc Time: O (n^2)? – kiki
@kiki Mauvais. La multiplication est une opération constante. n * n est une seule étape. Le calcul de la sortie de la barre est cependant linéaire. –
Comme mentionné par cᴏʟᴅsᴘᴇᴇᴅ, il est O (n) pour l'exécution et l'espace. Permettez-moi d'essayer de l'expliquer avec une relation de récurrence et une dérivation.
Pour l'exécution
Base case: T(0) = 1
Recurion : T(n) = T(n-1) + 1 (constant time for addition operation)
T(n) = T(n-1) + 1
= T(n-2) + 1 + 1
= T(n-3) + 1 + 1 + 1
= T(n-4) + 1 + 1 + 1 + 1
= T(n-4) + 4*1
...
= T(n-n) + n * 1
= T(0) + n * 1
= 1 + n
= O(n)
à la complexité de l'espace
Il y aura 'n' pile créé pour tous les appels récursifs. Donc, O (n) espace.
Remarque: La complexité de l'espace peut être réduite davantage avec une implémentation de récurrence de queue.
J'espère que ça aide!
Fixez vos retraits s'il vous plaît. –
@ChristianDean Tentative? :) OP: Combien de fois recycle-t-il la pile - cela devrait vous donner une idée de la complexité de l'espace et du temps. – AChampion
@AChampion Hmm, pourquoi cela n'a pas fonctionné pour moi: | –