Itérative et récursive versions de l'algorithme ont la complexité en même temps?

Dire, par exemple, l'itératif et récursif versions de la suite de Fibonacci. Ont-ils la complexité en même temps?

Il existe plusieurs algorithmes itératifs pour le calcul de la suite de Fibonacci et plusieurs récursive, avec divers degrés de complexité.
Je pense qu'on peut raisonnablement dire que si ils n'ont pas la même complexité, alors qu'ils ne sont pas itératif et récursif versions de "le même algorithme". Ils sont différents algorithmes, et bien sûr de différents algorithmes pour calculer le même résultat n'est pas nécessairement la même complexité. Cela dit, il est assez courant de se référer à des groupes d'algorithmes par le même nom. Par exemple quicksort se comporte différemment selon la façon dont vous choisissez le pivot et l'ordre dans lequel vous les deux côtés de la partition, mais toutes les possibilités sont généralement appelées "quicksort".
... et il s'ensuit, que de savoir si ou non les deux morceaux de code peut être décrit comme "le même algorithme" dépend dans certains cas, sur si oui ou non votre langue/compilateur met en œuvre la queue de la récursivité. Si une version récursive crée une pile d'appel qu'il n'a pas besoin, alors c'est une autre algorithme avec inférieure de l'espace de la complexité.
Et une probable crash bug 🙂

OriginalL'auteur user567879 | 2011-12-16