排序算法中的递归 - 总是坏的？

Question

Mergesort,quicksort可能是最知名的nlogn排序算法.在大多数情况下,他们的解释和c ++代码示例包含递归.但据我所知,当数据量很大时,我们会对递归进行理解,这会导致堆栈溢出的风险很大.那么忽略关于排序算法的递归解释是否合理是不能在现实生活中使用的？

Answer 1

但据我所知,当数据量很大时,我们会对递归进行理解,这会导致堆栈溢出的风险很大.

这取决于几件事:

• 这些天尾调用几乎总是被优化,所以你永远不会用尾递归来达到堆栈溢出,即使你递归O(2^N)次数(算法仍然很慢,但它不会溢出堆栈).
• 大多数排序算法会减少Log2(N)时间.每兆兆字节的数据排序达到40个级别 - 不足以溢出一堆能够在其内存中保存数TB的数据.

忽略关于排序算法的递归解释是否合理,以至于无法在现实生活中使用？

不,忽略这些解释是不合理的:如果算法在逻辑上是递归的,那么最佳解释也将是递归的.即使您使用循环使用动态分配的堆栈来实现算法以避免堆栈溢出,算法的性质仍然是递归的,因此理解正在发生的事情的最佳方式是假装进行递归调用.

Answer 2

使用O(n log n)排序算法,递归算法引起的调用堆栈高度通常是O(log n)(假设在每次递归迭代时相对平衡的问题大小划分)

在最糟糕的情况下,在一个天真的实现中,当数组已经排序时,总是使用最后一个元素作为数据透视,这种情况会发生异常.在这种情况下,你将有一个O(n^2)运行时并产生一个调用堆栈高度O(n).

(如果它可以帮助你想象:这有点类似于使用比BFS更少空间的DFS背后的基本原理 - 前者只跟踪一次调用堆栈中的一个"搜索路径",而后者跟踪所有这些)