algorithm - 算法复杂度

Question

我会有一个很笼统的问题。除了在学校作为程序员之外，您是否曾经必须真正计算（例如在纸上）算法的复杂性？如果..你能给我一个例子吗？

谢谢你 ：）

Answer 1

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

Answer 2

绝对 - 我们最近刚刚遇到了我们的应用程序的问题，它突然开始出现一些严重的减速。事实证明，我们在一个非常主要的函数中间有一个三次 (O(n^3)) 算法。它被隐藏在抽象层之下。弄清楚发生了什么需要绘制函数调用图并查看细节。

诚然，一旦我们这样做了，我就不需要应用任何数学来注意到 O(n^3) 算法，但这主要是因为在大学里 3 年的算法分析让我对三次算法有一个大致的感觉好像。

无论如何，事实证明 N 只增加了一点点，但它正处于从几百毫秒到几秒钟再到几分钟的风口浪尖 - 所以这个问题直到最近才出现.

在大多数情况下，您将使用已定义复杂性的预打包算法。快速排序是 O(n^2) 最坏情况和 O(n*log(n)) 平均情况，二分查找是 O(log(n)) 等等。库通常会指定它们的性能特征，而您只需需要担心它们是如何组成的。

Answer 3

在工作中，我们随便讨论解决问题的各种算法，复杂性发挥了作用。这绝不是我们必须对复杂性进行严格证明的事情，而只是一般的“我们可以做 X，但那会是 O(N^2)，这太过分了，因为我们可能会迭代数百万行。”

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

Answer 4

不知道你有没有把编程竞赛当成学校，但是要看你能不能在时限内解决一个竞赛问题（有指定的问题大小限制），你得通过考虑所用算法的复杂性。

Answer 5

当然！任何时候，你做的事情超过一百万次，你可能想要检查你的算法。

我做过的一个例子是，当我生成数百万张必须适合网格模式的图像时。抱歉 - 无法更具体地说明这一点。

Answer 6

是的。

一般来说，复杂性对于餐巾纸的猜测来说已经足够明显了，这对于开发来说是很好的，直到我达到需要测量性能的地步。在许多情况下，我担心的部分很好（即餐巾猜测已经足够好），而其他一些事情正在减慢软件的速度。在几乎所有情况下，遵循我的基本假设并稍后衡量性能是值得的。

但是，当我在编写时间要求非常严格的代码时，尤其是在图形渲染中，我确实会坐下来确定算法复杂性以及与以替代方式执行它相关的权衡。

今天我正在使用其他人的代码，而且速度非常慢。我真的不在乎 - 它可能需要 10 分钟，这对它增强的整个过程很重要。但是我不得不查看代码来修复一个错误，而这个人在循环中的循环中有循环，他们中的大多数人每次都以相同的方式搜索相同的列表以查找不同的元素。本质上，他改变了一个很好的数组函数，比如 func(i){return records[i];} 变成了一个可怕的搜索例程：

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

现实要糟糕得多，但你明白了。

你现在在学校学习这个的原因是你可以看到这些结构并自动对它们进行分类。您可能不需要实际计算或将其减少到一个很好的简洁复杂性数字，但如果您现在不手动操作并看到很多，您也将生成这样的代码，您只需没有线索。

-亚当

Answer 7

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

Answer 8

是和不是。

我正在编写一个工具来将一组包的 RPM 依赖项扁平化为一个链。显而易见的解决方案运行得太慢了，所以我稍微挖掘了一下记忆以记住O(n+m)图论课上的算法。我做了一些粗略的计算以确保它确实是O(n+m)，然后将其编写并投入生产:)