我正在上一门计算复杂性的课程，到目前为止给人的印象是，它对开发人员不会有太大帮助。

我可能是错的，但是如果我们以前走这条路，能否请我们举例说明复杂性理论如何在工作中为我们提供帮助？谢谢。

解决方案

一个很好的例子是，当老板告诉我们做一些程序时，我们可以通过使用计算复杂性理论证明，老板要我们做的事情是不可能的。

在某些时候，我们会遇到需要思考的问题。现实世界中有许多问题需要处理大量数据...

例如：

• 地图应用程序...类似于Google Maps-我们将如何处理全球道路数据并绘制它们？我们需要快速绘制它们！
• 物流应用...认为类固醇的旅行推销员
• 数据挖掘...所有大型企业都需要一个，我们将如何挖掘一个包含100个表和10m +行的数据库，并在趋势过时之前得出有用的结果？

参加计算复杂性课程将分析和选择/创建对这种情况有效的算法。

相信我，将系数从T(3n)降低到T(2n)这样简单的事情就可以在以天为单位(如果不是几个月)的情况下测量" n"时产生巨大的差异。

这是非常重要的。如果我们不了解如何估算并确定算法需要花费多长时间，那么最终我们将编写一些非常慢的代码。在编写算法时，我总是在考虑计算复杂性。编程时应该始终牢记这一点。

在许多情况下尤其如此，因为尽管应用程序可以在带有少量测试数据集的台式计算机上正常运行，但重要的是要了解应用程序上线后响应速度有多快，并且有成千上万的人使用它。

是的，有一天，当我不得不对一堆学生考试进行分类时，我对分类算法的知识就派上用场了。我使用了合并排序(但没有使用quicksort或者heapsort)。在编程时，我只使用库提供的任何排序例程。 (还不必对大量数据进行排序。)

我一直在程序设计中使用复杂性理论，主要是在决定使用哪种数据结构时，在决定是否或者何时对事物进行排序时以及进行许多其他决策时。

对于大多数类型的编程工作，理论部分和证明本身可能并没有用，但是他们正在做的是使我们能够立即说出"此算法为O(n ^ 2)，因此我们可以"。不能在这100万个数据点上运行它"。即使在最基本的处理大量数据的过程中，我们也会遇到这种情况。

快速思考复杂性理论对我在业务数据处理，GIS，图形编程和总体理解算法中很重要。与通常需要自学的课程相比，这是我们从CS学习中可获得的最有用的课程之一。

的确，在对算法复杂性没有丝毫了解的情况下，人们可以在软件开发中真正走得很远。我发现我一直都在使用我的复杂性知识；但是，在这一点上通常是没有意识到的。学习复杂性给软件开发人员带来的两件事是比较做同样事情的非相似算法的一种方法(排序算法是经典示例，但大多数人实际上并不编写自己的排序)。它给我们带来的更有用的东西是一种快速描述算法的方法。

例如，考虑使用SQL。每天都有大量的程序员使用SQL。如果我们看到以下查询，那么如果我们已经研究了复杂性，那么我们对该查询的理解就会大不相同。

SELECT User.*, COUNT(Order.*) OrderCount FROM User Join Order ON User.UserId = Order.UserId

如果我们研究过复杂性，那么我们会理解，如果有人说某个DBMS的复杂度为O(n ^ 2)。没有复杂性理论，该人将不得不解释表扫描等问题。如果我们向订单表添加索引

CREATE INDEX ORDER_USERID ON Order(UserId)

那么上面的查询可能是O(n log n)，这对于大型DB而言将有很大的不同，但是对于小型DB则完全没有。

有人可能会争辩说，不需要复杂性理论来理解数据库的工作原理，它们是正确的，但是复杂性理论提供了一种用于思考和讨论对数据起作用的算法的语言。

是和否

是的)在开发和实现算法时，我经常使用大的O表示法。
例如。当我们应该处理10 ^ 3项并且第一个算法的复杂度为O(n log(n))而第二个算法的复杂度为O(n ^ 3)时，我们可以简单地说第一个算法几乎是实时的，而第二个则需要大量的计算。

有时，有关NP复杂性类别的知识可能会很有用。它可以认识到，当某些NP完全问题可以简化为我们正在考虑的问题时，我们就可以停止考虑发明有效的算法。

否)我上面所描述的只是复杂性理论的一小部分。结果，很难说我使用它，我使用了它的次要部分。

我应该承认，有许多软件开发项目并未以复杂的方式涉及算法的开发或者使用。在这种情况下，复杂性理论是无用的。普通算法用户经常使用单词"快"和"慢"，" x秒"等进行操作。

O(1)：无循环的纯代码。只是流过。查找表中的查找也是O(1)。

O(log(n))：有效优化的算法。示例：二叉树算法和二叉搜索。通常不会受伤。如果我们手头有这样的算法，那么我们会很幸运。

O(n)：单个数据循环。非常大的伤害

O(n * log(n))：一种执行某种分而治之策略的算法。大伤n。典型示例：合并排序

O(n * n)：某种嵌套循环。即使是小n也会受伤。与朴素矩阵计算通用。如果可以的话，我们想避免这种算法。

O(n ^ x for x> 2)：具有多个嵌套循环的邪恶结构。很小的伤害

O(x ^ n，n！甚至更糟)：我们不希望在生产代码中使用怪异的(并且经常是递归的)算法，除非在非常受控制的情况下，否则对于很小的n，如果真的没有更好的选择。计算时间可能会随着n = n + 1激增。

将算法从更高复杂度的类中移下来可以使算法飞速发展。考虑一下傅立叶变换，它具有一个O(n * n)算法，该算法在极少数情况下无法在1960年代的硬件上使用。然后，Cooley和Tukey通过重新使用已经计算出的值，巧妙地降低了复杂度。这导致将FFT广泛引入信号处理中。最后，这也是为什么史蒂夫·乔布斯(Steve Jobs)用iPod发大财的原因。

一个简单的例子：天真的C程序员编写了这样的循环：

for (int cnt=0; cnt < strlen(s) ; cnt++) {
  /* some code */
}

由于strlen()的实现，所以这是一个O(n * n)算法。嵌套循环导致big-O内部的复杂性倍增。 O(n)内的O(n)给出O(n * n)。 O(n)内的O(n ^ 3)给出O(n ^ 4)。在该示例中，预先计算字符串长度将立即将循环变成O(n)。乔尔(Joel)也曾写过这本书。

但是，复杂性级别并不是全部。我们必须注意n的大小。如果由于重新加工而导致(现在线性的)指令数量大量增加，则将O(n * log(n))算法重新加工为O(n)将无济于事。而且如果n仍然很小，那么优化也不会带来太大的效果。

电脑不是很聪明，它们会按照指示进行操作。编译器可以为我们稍微优化代码，但不能优化算法。人脑的工作方式不同，这就是为什么我们需要了解大O的原因。请考虑计算斐波那契数。我们都知道F(n)= F(n-1)+ F(n-2)，并且从1,1开始，我们可以轻松地在线性时间内轻松计算以下数字。但是，如果我们告诉计算机使用该公式(递归地)进行计算，则它不是线性的(至少在命令式语言中)。不知何故，我们的大脑优化了算法，但是编译器无法做到这一点。因此，我们必须努力改进算法。

然后，我们需要进行培训，以发现看似显而易见的大脑优化，查看代码何时可能无效，了解坏算法和好的算法的模式(就计算复杂性而言)等等。基本上，这些课程提供以下几项服务：

• 了解执行模式和数据结构，以及它们对程序需要完成的时间有何影响；
• 训练思维，找出可能对大型数据集无效的算法中的潜在问题。或者了解分析结果；
• 学习通过减少算法的计算复杂度来改进算法的众所周知的方法；
• 准备好在很棒的公司通过面试:)

是的，我经常使用Big-O表示法，或者更确切地说，我使用其背后的思维过程，而不是表示法本身。很大程度上是因为组织中的开发人员很少，所以我经常理解它。我并不是要对那些人不敬，但是根据我的经验，对这些东西的了解是"使男人和男孩分居"的事情之一。

我想知道这是否是只能接受"是"的问题之一？令我惊讶的是，了解计算复杂性的人们大致等同于认为重要的人们。因此，可能回答"否"的任何人可能都不理解该问题，因此会跳到下一个问题，而不是停下来回答。只是一个想法 ;-)

这里有很多好的建议，而且我敢肯定，大多数程序员都会偶尔使用他们的复杂性知识。

但是，我应该说，了解计算复杂性在游戏领域中至关重要！是的，我们听说过，"无用"的东西是游戏编程赖以生存的东西。

我敢打赌，很少有专业人士像游戏程序员那样关心Big-O。

@马丁：我们能详细说明其背后的思想过程吗？

它可能不像坐下来为解决方案制定Big-O标记那样明确，但是它可以使我们意识到问题，并引导我们寻求更有效的答案，并避免可能采取的方法中的问题。例如O(n * n)与更快的速度例如搜索存储在列表中的单词而不是存储在trie中的单词(伪造的示例)

我发现这与我将选择使用的数据结构以及如何处理大量记录的方式有所不同。

我会定期使用复杂度计算，这主要是因为我在地理空间领域中使用非常大的数据集，例如涉及数百万甚至数十亿笛卡尔坐标的过程。一旦开始遇到多维问题，复杂性就可能成为一个现实问题，因为一维为O(n)的贪婪算法突然跳至三个维为O(n ^ 3)，并且不需要太多数据造成严重的瓶颈。正如我在类似的文章中提到的那样，当我们开始处理大小不同的复杂对象组时，我们还会看到大的O符号变得很麻烦。复杂性的顺序也可能取决于数据，对于精心设计的ad hoc算法，典型情况下的性能要比一般情况下好得多。

值得一提的是，在探查器下测试算法，以查看设计的内容是否达到了目标。我发现，由于所有明显的原因，通过算法调整解决大多数瓶颈要比提高处理器速度要好得多。

对于一般算法及其复杂性的更多阅读，我发现Sedgewicks既可提供信息，又可访问。对于空间算法，关于计算几何的O'Rourkes书籍非常出色。

在正常生活中，应该在计算机附近而不是计算机附近应用复杂性和并行处理的概念。这将使我们效率更高。缓存一致性。之类的东西。