complexité des fonctions récursives - Le temps et l'espace

Question

Je souhaite savoir comment calculer le temps et la complexité de l'espace des fonctions récursives comme permutation, fibonacci (décrit here)

En général, nous pouvons avoir récursion à beaucoup d'endroits que tout à permutaion ou récursion, donc je suis à la recherche d'approche généralement suivie pour calculer la complexité de l'espace TMIE ans de

Merci

Answer 1

Jetez un oeil à http://www.cs.duke.edu/~ola/ap/recurrence.html

Answer 2

La complexité temporelle et la complexité de l'espace sont les deux éléments qui caractérisent les performances d'un algorithme. De nos jours, comme l'espace est relativement peu coûteux, les gens se soucient surtout de la complexité du temps, et la complexité temporelle s'exprime principalement en termes de relation de récurrence. Envisager un algorithme de recherche binaire (Recherche d'un élément dans un tableau): chaque fois que l'élément central (mi) est sélectionné et comparé à l'élément (x) à rechercher. Si (mid> x), recherchez le sous-tableau inférieur, sinon recherchez le sous-tableau supérieur. S'il y a n éléments dans un tableau, et que T (n) représente la complexité temporelle de l'algorithme, alors T (n) = T (n/2) + c, où c est une constante. Avec des conditions aux limites données, on peut résoudre pour T (n), dans ce cas, ce serait T (n) = log (n), avec T (1) = 1.