Mergesort, Quicksort sont probablement les plus connus d'algorithmes de tri de Nlogn. Leurs exemples d'explication et de code C ++ dans la plupart des cas contiennent une récursion. Mais autant que je sache la récursivité lorsqu'il s'agira d'une grande quantité de données, nous courons un gros risque de débordement de pile. Il est donc raisonnable d'ignorer l'explication de la récursion sur le tri des algorithmes en tant que telle qui ne peut pas être utile dans la vie réelle?
4 Réponses :
avec L'exception se produit dans le scénario pire des cas de QuickSort sur une implémentation naïve qui utilise toujours le dernier élément en tant que pivot lorsque le tableau est déjà trié, auquel cas vous auriez un (Si cela vous aide à visualiser: Ceci est quelque peu analogue à la raison d'être derrière les DFS en utilisant moins d'espace que BFS - le premier n'emporte qu'une piste d'un "chemin de recherche" dans la pile d'appels à la fois, tandis que ce dernier garde la trace de tous) O (n journal n) algorithmes de tri, la hauteur de la pile d'appels engagée par l'algorithme récursif est généralement O (journal n) (en supposant une division relativement équilibrée du problème taille à chaque itération récursive)
O (n ^ 2) heure d'exécution et incruster une hauteur de pile d'appels de O (n) .
dans un Pour donner un exemple concret, Les choses sont problématiques si la profondeur de la récursion est autorisée à croître comme, disons, O (n logn) algorithme, nous examinons généralement log2 (n) niveaux de récursion.
log2 (1 000 000 000) = 30 , donc un risque majeur de débordement de pile.
O (n) . Un algorithme évolutif devrait s'assurer que cela n'arrive pas.
mais aussi loin que je comprenne à propos de la récursion lorsqu'il s'agira d'une grande quantité de données, nous courons un gros risque de débordement de pile.
Cela dépend de plusieurs choses:
- Les appels quotidiennes sont presque toujours optimisés ces jours-ci, de sorte que vous ne frapperiez jamais de débordement de pile Avec la récursion de la queue, même si vous recursez
O (2 ^ n) fois (l'algorithme serait toujours lent, mais cela ne déboucherait pas la pile).- La plupart des algorithmes de tri recurse Down
log2 (n) fois. Cela vient jusqu'à 40 niveaux par téraoctet de données triés - pas assez pour déborder une pile de quoi que ce soit capable de détenir un téraoctet de données dans sa mémoire.est-il raisonnable d'ignorer l'explication de la récursion sur le tri des algorithmes en tant que tels qui ne peuvent pas être utilisés dans la vie réelle?
Non, il n'est pas raisonnable d'ignorer ces explications: si un algorithme est logiquement récursif, la meilleure explication sera également récursive. Même si vous implémentez l'algorithme avec une boucle qui utilise une pile allouée dynamiquement pour éviter les débordements de pile, la nature de l'algorithme resterait récursif, de sorte que la meilleure façon de comprendre ce qui se passe est de prétendre qu'un appel récursif est fait.
Comme d'autres ont souligné, la profondeur de la pile est égale au niveau de récursivité le plus profond qui est typiquement du journal de commande (n).
Le "problème" avec la récursion est généralement la surcharge impliquée dans la fabrication d'un appel de méthode et de passer des paramètres. Par exemple, considérez une méthode factorielle
int motifial (int k) {if (k == 1) renvoie 1 autre retour k * factorial (k-1);}
Si vous appelez ceci avec n = 21, vous effectuez 20 multiplications, mais vous avez également les frais généraux de la configuration et de revenir à partir de 20 appels de méthodes - beaucoup plus de travail. Si vous souhaitez utiliser un algorithme récursif, vous pourrez peut-être configurer une pile privée et utiliser une boucle tandis que vous pouvez mettre en œuvre l'algorithme sans beaucoup d'appels de méthode (relativement coûteux). Bien sûr, l'amélioration (le cas échéant) sera spécifique de la langue.
La récursion est mauvaise si vous avez n niveaux. Si vous pouvez casser le travail en deux appels récursifs (la moitié des données) ou plus, vous évitez le problème du débordement de la pile.
Je ne pense pas que vous puissiez citer quoi que ce soit dans le domaine de la programmation qui est «toujours mauvais». (Eh bien, certains argument que l'installation de Windows sur une machine peut être un exemple, mais c'est une autre question.)
Récursion est quelque chose à utiliser quand il est nécessaire. Dans certains cas, y compris plusieurs algorithmes de tri, le code récursif est beaucoup plus simple et plus propre que toute représentation alternative et la profondeur maximale est raisonnable.
Le risque de dépassement de pile n'existe que dans de mauvaises implémentations qui allouent beaucoup de mémoire en tant que variables locales, telles que les tableaux de valeur de la valeur de la valeur de Pascal. La profondeur des appels récursifs n'est pas un problème si la fonction récursive n'allocie que 2-3 points sur la pile.