算法复杂度

Question

我有一个比较普遍的问题。作为程序员，除了在学校之外，你是否曾经需要真正计算（例如在纸上）算法的复杂度？如果是的话，请举个例子。

谢谢 :)

- michal

Answer 1

如果你正在编写一款软件，并且可以想到多种实现方式，通常决定因素之一（除了概念复杂度和实现时间）将是算法复杂度。因此，当你的老板要求你为你的决策提供理由时，需要弄清楚每个算法的复杂度。虽然有些人可能认为这是一种过早优化的形式，但我认为共识是选择适合你问题的设计只是良好的软件工程。

- rmeador

Answer 2

当然可以 - 我们最近的应用程序出现了一些突然的严重减速问题。原来我们在一个非常重要的函数中间有一个立方（O（n ^ 3））算法。它隐藏在多层抽象之下。弄清楚发生了什么需要绘制函数调用图并查看详细信息。

当然，一旦我们做到了这一点，我就不必应用任何数学知识来注意到立方算法，但这主要是因为我在大学里三年的算法分析给了我对立方算法的一般感觉。

总之，事实证明N只是稍微增加了一点，但它恰恰处于从几百毫秒到几秒甚至几分钟的过度，因此该问题直到最近才出现。

大多数时候，您将使用已定义复杂度的预打包算法。 快速排序的最坏情况是O（n ^ 2），平均情况是O（n * log（n）），二分搜索是O（log（n）），等等。库通常会指定其性能特征，您只需要关心它们的组成方式。

- Josh

Answer 3

在工作中，我们会随意地讨论各种算法来解决问题，并且复杂度会起到作用。我们从不需要对复杂度进行严格的证明，只是一般性地认为“我们可以做X，但这将是O(N^2)，因为我们可能要遍历数百万行。”

过度优化可能导致糟糕的代码，但了解基本算法的复杂度在确定最佳解决编程问题的方法方面有很大帮助。

- Dan Lew

Answer 4

我不知道你是否认为编程竞赛属于学校范畴，但为了确定你能否在规定时间内解决竞赛问题（满足指定的问题大小限制），你必须通过考虑所使用算法的复杂度大致估计操作次数。

- Mehrdad Afshari

Answer 5

当然！随时，如果您要重复执行一百万次某个操作，您可能需要检查算法。

例如，我曾经生成过数百万张图像，并且这些图像必须适合网格模式。对于这个例子，我不能提供更具体的信息。

- Eric Wendelin

Answer 6

我不知道自己是否真的会把事情写下来，但我一直在评估我的算法构建方式，看看能否提高其效率。对于代码，我会问自己是否有办法将嵌套循环转换为单个循环或从循环转换为使用分治方法。这相当于从O(N²)到O(N)和从O(N)到O(log₂N)。SQL也是如此--我能否删除一个连接并使用索引代替子查询--也许从O(N²)到O(N)（甚至是O(1)，如果它使我能够在两个表上进行索引查询）。

- tvanfosson

---

你有提到的那个 SQL 的例子吗？因为带索引的连接和子查询大致相同（通常一个是使用另一个来实现）。 - Javier

我并没有考虑具体的例子，只是想到了一般的过程。 - tvanfosson

使用SQL可能很简单，只需注意添加索引即可使其使用不同的算法，从而更高效。 - tvanfosson

Answer 7

是和不是。

我在编写一个工具，将一组软件包的RPM依赖关系展开为单个链。显而易见的解决方案运行速度太慢了，所以我从记忆中挖掘出了一个来自图论课程的O(n+m)算法。我进行了一些草稿计算，确保它真的是O(n+m)，然后编写并投入生产 :)。

- ephemient

Answer 8

是的。

一般来说，复杂度对于草图猜测来说是显而易见的，这对于开发来说是可以接受的，直到我需要测量性能。在许多情况下，我担心的部分没问题（即，草图猜测足够好），而其他一些东西正在减慢软件的速度。在几乎所有情况下，坚持我的基本假设并稍后测量性能都是值得的。

然而，当我编写非常时间关键的代码，特别是在图形渲染方面时，我会坐下来确定算法复杂度和采用替代方法所涉及的权衡。

今天我正在使用别人的代码，但它运行得非常慢。我并不是很在意——它可能需要10分钟才能完成整个流程，但我必须查看代码以修复错误，而这个人使用了嵌套循环，在大部分循环中每次搜索相同的列表以寻找不同的元素。实质上，他已经将一个很好的数组函数（比如func(i){return records[i];}）变成了一个可怕的搜索程序：

func(i)
{
   for each index in records
      if i==index return records[index]
   next
}

实际情况比这更糟，但你可以理解这个概念。

你现在在学校学习这个的原因是为了让你看到这些结构并自动分类。你可能不需要真正地计算机或将其简化为一个漂亮的复杂度数字，但如果你现在不手动操作并且看到很多这样的代码，那么你也会像那样生成代码，而你将毫无头绪。

-Adam

- Adam Davis