Рекурсия в алгоритмах сортировки — всегда плохо?
Mergesort, quicksort, вероятно, являются наиболее известными алгоритмами сортировки nlogn. Их объяснение и примеры кода на C ++ в большинстве случаев содержат рекурсию. Но, насколько я понимаю, о рекурсии, когда это будет большой объем данных, мы рискуем переполнить стек. Так разумно ли игнорировать рекурсивное объяснение алгоритмов сортировки как таковых, которые нельзя использовать в реальной жизни?
Решение
Но, насколько я понимаю, о рекурсии, когда это будет большой объем данных, мы рискуем переполнить стек.
Это зависит от нескольких вещей:
- Хвостовые звонки в наши дни почти всегда оптимизируются, поэтому вы никогда не столкнетесь с переполнением стека с помощью хвостовой рекурсии, даже если вы рекурсивны
O(2^N)раз (алгоритм все равно будет медленным, но не будет переполнять стек). - Большинство алгоритмов сортировки повторяются
Log2(N)раз. Это позволяет получить до 40 уровней на терабайт сортируемых данных — этого недостаточно, чтобы переполнить стек чего-либо, способного удержать терабайт данных в его памяти.
Разумно ли игнорировать рекурсивное объяснение алгоритмов сортировки как таковых, которые нельзя использовать в реальной жизни?
Нет, не стоит игнорировать эти объяснения: если алгоритм является логически рекурсивным, лучшее объяснение также будет рекурсивным. Даже если вы реализуете алгоритм с циклом, который использует динамически распределенный стек, чтобы избежать переполнения стека, природа алгоритма останется рекурсивной, поэтому лучший способ понять, что происходит, — притвориться, что сделан рекурсивный вызов.
Другие решения
С O(n log n) В алгоритмах сортировки высота стека вызовов, создаваемая рекурсивным алгоритмом, обычно O(log n) (Предполагая относительно сбалансированное деление размера задачи на каждой рекурсивной итерации)
Исключение происходит в наихудшем сценарии быстрой сортировки на простой реализации, которая всегда использует последний элемент в качестве сводной, когда массив уже отсортирован, и в этом случае у вас будет O(n^2) время выполнения и нести высоту стека вызовов O(n),
(Если это помогает вам визуализировать: это несколько похоже на обоснование DFS, использующего меньше места, чем BFS — первый отслеживает только один «путь поиска» в стеке вызовов за раз, тогда как последний отслеживает все из них )
В O(n logn) алгоритм, мы обычно смотрим на log2(n) уровни рекурсии.
Чтобы привести конкретный пример, log2(1,000,000,000) = 30, так что вряд ли основной риск переполнения стека.
Вещи становятся проблематичными, если глубина рекурсии увеличивается, скажем, O(n), Масштабируемый алгоритм должен гарантировать, что этого не произойдет.
Как уже отмечали другие, глубина стека равна самому глубокому уровню рекурсии, который обычно равен порядку log (n).
«Проблема» с рекурсией, как правило, заключается в накладных расходах, связанных с вызовом метода и передачей параметров. Например, рассмотрим факторный метод
int factorial (int k)
{если (k == 1) вернуть 1, иначе вернуть k * factorial (k-1);}
Если вы вызываете это с n = 21, то вы делаете 20 умножений, но у вас также есть накладные расходы на настройку и возврат из 20 вызовов методов — намного больше работы. Если вы хотите использовать рекурсивный алгоритм, вы можете установить частный стек и использовать цикл while для реализации алгоритма без большого количества (сравнительно дорогих) вызовов методов. Конечно, улучшение (если есть) будет зависеть от языка.