寻求最佳算法（渐近地）并忽略其他细节

Question

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

我们以 Theta(n^2) 为例。

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

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

我的问题如下：

如果渐进地随着 N 变得越来越大，递归（即分而治之的方法）表现得更好，当我们对 N 的巨大输入进行递归时，忽略这一点不是不现实吗？最终可能会耗尽堆栈吗？
由于投入巨大，我们实际上永远不会得到结果。

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

Answer 1

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

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

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

Answer 2

这是我第一次在快速排序中看到的一个有用的技巧：

f(x)
{
  for (;;)
  {
    if (x is trivial)
    {
      return;
    }
    x1 = one half of problem x
    x2 = other half of problem x
    if (x1 is the little half)
    {
      x = x2;
      f(x1);
    }
    else
    {
      x = x1;
      f(x2);
    }
  }
}

这样做的要点是，每个递归调用都针对问题的一小半 - 通常小于原始问题大小的一半 - 而问题的较大一半是通过迭代完成。如果问题的大小为 2^n，则堆栈的大小只需为 n，即使由于分裂非常不均匀，您最终花费的时间接近 n^2 而不是 n log n。

至于使用 n log n 时间但加载堆栈的算法的“实际成本”，请注意，在 n log n 时间内运行的算法没有时间使用超过 n log n 的内存，因此加载和堆栈负载实际上不可能是大量内存，尽管它可能足以使 Java 解释器在您的递归失控的印象下崩溃。