performance - 寻求最佳算法(渐近)并忽略其他细节

Question

在某些情况下，对问题的蛮力方法具有复杂性，在性能方面不够好。

让我们举个例子西塔(n^2)。

使用递归方法可以将其改进为 Theta(nlogn)。

显然，渐近地人们会选择使用递归方法，因为对于越来越大的输入 N，增长阶数越低，即性能越好。

我的问题如下:

如果渐近地随着 N 变得越来越大，递归(即分而治之方法)表现得更好，那么在我们递归 N 的巨大输入时忽略它是不是不现实的，我们最终可以运行堆栈不足？
由于大量的投入，我们实际上永远得不到结果。

那么，如果忽略这些细节，我们如何才能确定我们为特定问题选择了最佳算法呢？

Answer 1

可以在不使用硬件堆栈的情况下实现递归算法。如果堆栈溢出的可能性是一个严重的问题，您可以实现自己的堆栈或简单地限制递归的深度。

但是，如果算法以递归方式划分一组数据(大小为 n)，则递归次数将与 log n< 成正比。这意味着要耗尽大小为 s 的堆栈，您需要大小为 2^s 的数据，随着 s 的增长速度非常快.人们往往不会意识到指数函数增长的速度有多快。我的观点是，使用这种类型的算法(在每个递归步骤中拆分一组数据)，输入数据不太可能大到需要如此多的递归以耗尽堆栈。

编辑:但是我不是专业的程序员，所以我缺乏实践经验。