算法的复杂性

Question

我会有一个相当普遍的问题。你有没有必要真正计算（例如在论文中）算法的复杂性，除了在学校作为程序员？如果......请给我举个例子。

谢谢:)

Answer 1

我不知道，如果你认为编程竞赛为学校与否，而是看你是否能在时限解决比赛问题（与指定问题规模的限制），您必须通过考虑所用算法的复杂性粗略估计操作次数。

Answer 2

如果你正在编写一个软件，你能想到的多种方式来实现它，往往是决定因素之一（除了概念上的复杂性和时间来实现）将是算法的复杂性。因此，当你的老板想为你的决定辩护时，弄清楚每一项的复杂性是必要的。虽然有些人可能认为这是一种不成熟的优化方式，但我认为，共识是选择适合您问题的设计只是一个好的软件工程。

Answer 3

在工作中，我们随便讨论了不同的算法来解决问题，而复杂性起着其作用。这绝不是我们必须对复杂性进行严格证明的原因，而只是一个将军“我们可以做X，但那会是O（N^2），这太多了，因为我们可能迭代数百万行”。

过度优化可能会导致糟糕的代码，但我们知道的你的基本算法的复杂度去确定解决规划问题的最好办法很长的路要走。

Answer 4

当然！任何时候，你正在做超过一百万次的事情，你可能想要检查你的算法。当我产生数百万不得不适应网格图案图像的

一个实例我所做的。对不起 - 无法获得更具体的那一个。

Answer 5

当然 - 我们最近刚刚与我们的应用程序的问题，即它突然开始打一些主要放缓。原来我们有一个立方（O（n^3））算法就在一个非常重要的函数中。它一直隐藏在抽象层之下。弄清楚发生了什么事情需要绘制函数调用图并查看细节。

无可否认，一旦我们这样做了，这不像我必须运用任何数学来注意O（n^3）算法，但这主要是因为大学3年的算法分析给了我一个普遍的感觉什么是立方算法。

无论如何，事实证明，N增加了一点点，但它恰好处于从几百毫秒开始，花费几秒钟，然后进入几分钟 - 因此问题没有显示直到最近。

在大多数情况下，你将要使用已定义的复杂性预包装算法。快速排序是O（n^2）最差情况和O（n * log（n））平均情况，二进制搜索是O（log（n））等。库通常会指定它们的性能特征，而您需要担心他们是如何构成的。

Answer 6

是的。

一般的复杂性是餐巾纸猜测明显不够，这很好的发展，直到我得到的地方，我需要衡量业绩的地步。在许多情况下，我担心的部分没有问题（例如，餐巾纸的猜测足够好），而其他的东西则会降低软件的速度。在几乎所有情况下，我都会支付我的基本假设，并在稍后测量绩效。然而，当我在做非常时间关键的代码时，尤其是在图形渲染时，我确实坐下来确定算法的复杂性和与替代方式相关的折衷。

今天我正在与别人的代码工作，它的速度非常慢。我并不在乎 - 对于它所提升的整个过程而言，所需时间可能需要10分钟。但是我必须看代码来修复一个bug，并且这个人在循环内的循环中有循环，大多数人每次都以相同的方式搜索同一个不同的元素。从本质上说，他已经改变一个不错的arrayfunction，说FUNC（我）{返回记录[我];}成一个可怕的搜索程序：

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)，然后将其写入并投入生产:)