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 🙂
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
Vous devez vous connecter pour publier un commentaire.
La réponse dépend fortement de votre mise en œuvre. Pour l'exemple que vous avez donné il y a plusieurs solutions possibles, et je dirais que les naïfs façon de mettre en œuvre une solution a mieux la complexité lors de la mise en œuvre itérative. Voici les deux implémentations:
Dans les deux implémentations j'ai pris une entrée correcte, c'est à dire n >= 1. Le premier code est beaucoup plus long, mais sa complexité est O(n) c'est à dire linéaire, tandis que la seconde mise en œuvre est plus courte, mais a exponentielle de la complexité O(fib(n)) = O(φ^n) (
φ = (1+√5)/2
) et est donc beaucoup plus lent.On peut améliorer une version récursive par l'introduction de memoization(c'est à dire de rappeler les valeurs de retour de la fonction vous avez déjà calculé). Cela se fait généralement par l'introduction d'un tableau dans lequel vous stocker les valeurs. Voici un exemple:
Ici la complexité de l'algorithme récursif est linéaire comme la solution itérative. La solution que j'ai présenté ci-dessus est l'approche top-down pour la programmation dynamique la solution de votre problème. L'approche bottom-up va mener à quelque chose de très similaire à la solution que j'ai présenté comme itératif.
Il y a beaucoup d'articles sur la programmation dynamique, y compris dans wikipédia
Selon les problèmes que j'ai rencontré dans mon expérience, certains sont beaucoup plus difficile à résoudre dans l'approche bottom-up(c'est à dire solution itérative), tandis que d'autres sont difficiles à résoudre avec une approche top-down.
Cependant, la théorie stipule que chaque problème a une solution itérative est un appel récursif avec la même complexité de calcul (et vice versa).
Espère que cette réponse vous aide.
mem[n-2]
.I would say that the naive way to implement a solution has better complexity when implemented iterative.
Je dirais que la version itérative n'est pas naïf plus. Le problème avec la suite de Fibonacci, c'est qu'il est très facile d'écrire de façon exponentielle une version récursive, mais l'écriture exponentielle itératif version est dur, de sorte que la première version vient avec lors de l'écriture d'un algorithme itératif n'est pas vraiment naïf, vous devez avoir investi un peu de la pensée à venir avec de l'itération.OriginalL'auteur Ivaylo Strandjev
Le particulier algorithme récursif pour le calcul fibanocci de la série est de moins en moins efficace.
Considérons la situation suivante de trouver fib(4) par le biais de l'algorithme récursif
Maintenant, quand l'algorithme ci-dessus s'exécute pour n=4
C'est un arbre. Il dit que pour le calcul de fib(4) vous devez calculer fib(3) et fib(2) et ainsi de suite.
Avis que, même pour une petite valeur de 4, fib(2) est calculé deux fois et fib(1) est calculé à trois fois. Ce nombre d'ajouts de pousse pour les grands nombres.
Il y a une conjecture que le nombre d'ajouts nécessaires pour le calcul de fib(n) est
Donc cette duplication est celle qui est la cause de la diminution des performances de cet algorithme.
L'algorithme itératif pour la suite de fibonacci est beaucoup plus rapide car il n'implique pas de calcul de la redondante choses.
Il peut ne pas être le même cas pour tous les algorithmes.
OriginalL'auteur Vinoth Kumar C M
Si vous prenez certains algorithme récursif, vous pouvez le convertir itératif par le stockage de toutes les fonctions de variables locales dans un tableau, simulant en pile sur le tas. Si c'est fait comme cela, il n'y a pas de différence entre itératif et récursif.
Noter qu'il y a (au moins) deux récursive de Fibonacci algorithmes, donc pour l'exemple pour être exact, vous devez spécifier quel algorithme récursif vous parlez.
OriginalL'auteur Dialecticus
Oui, chaque algorithme itératif peut être transformé en une version récursive et vice versa. Une façon par le passage de continuations et l'autre par la mise en œuvre de la pile de la structure. Cela se fait sans augmentation du temps de la complexité.
Si vous pouvez optimiser tail-recursion puis chaque algorithme itératif peut être transformé pour récursive sans augmenter asymptotique de la complexité de la mémoire.
OriginalL'auteur soulcheck
Oui, si vous utilisez exactement les mêmes idées sous-jacentes de l'algorithme, il n'a pas d'importance. Cependant, la récursivité est souvent facile à utiliser à l'égard de l'itération. Par exemple, l'écriture d'une version récursive de la tours de Hanoï est assez facile. Transformer une version récursive dans une correspondante de la version itérative est difficile et sujette aux erreurs, même si cela peut être fait. En fait, il est le théorème qui affirme que chaque algorithme récursif peut être transformé en un équivalent itératif un (cette opération nécessite imitant la récursivité de manière itérative en utilisant une ou plusieurs données de pile structures de tenir des paramètres passés à récursive invocations).
OriginalL'auteur Massimo Cafaro