25

我正在学习计算复杂性课程，到目前为止，我的印象是它对开发人员没有太大帮助。

我可能是错的，但如果你以前走这条路，你能否提供一个例子来说明复杂性理论如何帮助你的工作？非常感谢。

4

14 回答 14

51

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

O(log(n))：有效优化的算法。示例：二叉树算法和二叉搜索。一般不会疼。如果你手头有这样的算法，你会很幸运。

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

O(n*log(n))：一种执行某种分而治之策略的算法。对大 n 有害。典型例子：归并排序

O(n*n)：某种嵌套循环。即使 n 很小也会很痛。常见于朴素矩阵计算。如果可以的话，你想避免这种算法。

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

O(x^n, n! 甚至更糟)：你不希望在生产代码中使用怪异的（通常是递归的）算法，除非在非常受控的情况下，对于非常小的 n 并且如果真的没有更好的选择。计算时间可能会在 n=n+1 时爆炸式增长。

将你的算法从更高复杂度的类中下移可以使你的算法飞起来。想想傅里叶变换，它的 O(n*n) 算法在 1960 年代的硬件上无法使用，除非在极少数情况下。然后 Cooley 和 Tukey 通过重新使用已经计算的值，巧妙地降低了复杂性。这导致 FFT 广泛应用于信号处理。最后，这也是史蒂夫乔布斯通过 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)。乔尔也写过这个。

然而，复杂性类别并不是一切。你必须留意 n 的大小。如果（现在是线性）指令的数量由于返工而大量增长，将 O(n*log(n)) 算法返工为 O(n) 将无济于事。如果 n 仍然很小，那么优化也不会产生太大的影响。

于 2008-09-21T19:41:53.577 回答
10

尽管对算法复杂性一无所知，但确实可以在软件开发中走得很远。我发现我一直在使用我对复杂性的了解；但是，在这一点上，它通常是没有意识到的。作为软件开发人员，学习复杂性为您提供的两件事是一种比较做同样事情的非相似算法的方法（排序算法是典型的例子，但大多数人实际上并没有编写自己的排序算法）。它为您提供的更有用的东西是一种快速描述算法的方法。

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

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

如果您研究过复杂性，那么您会理解是否有人说某个 DBMS 的复杂性是 O(n^2)。如果没有复杂性理论，这个人将不得不解释表扫描等。如果我们在 Order 表中添加索引

CREATE INDEX ORDER_USERID ON Order(UserId)

那么上面的查询可能是 O(n log n)，这对于大型 DB 会产生巨大的影响，但对于小型 DB，它根本不算什么。

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

于 2008-09-21T17:39:37.567 回答
6

对于大多数类型的编程工作，理论部分和证明本身可能没有用，但他们正在做的是尝试给你一种能够立即说“这个算法是 O(n^2) 所以我们可以”的直觉不要在这 100 万个数据点上运行它”。即使在对大量数据进行最基本的处理时，您也会遇到这种情况。

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

于 2008-09-21T17:28:50.697 回答
4

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

然后，您需要进行培训，以发现看起来如此明显的大脑优化，查看代码何时可能无效，了解坏算法和好算法的模式（就计算复杂性而言）等等。基本上，这些课程有几件事：

  • 了解执行模式和数据结构以及它们对您的程序需要完成的时间有什么影响；
  • 当算法在大型数据集上可能效率低下时，训练您的思维来发现算法中的潜在问题。或者了解分析的结果；
  • 学习通过降低计算复杂度来改进算法的众所周知的方法；
  • 准备自己通过酷公司的面试:)
于 2008-09-21T20:15:09.517 回答
2

这是极其重要的。如果您不了解如何估计和计算出您的算法需要运行多长时间，那么您最终会编写一些非常慢的代码。在编写算法时，我一直在考虑计算复杂性。编程时应该始终牢记这一点。

在许多情况下尤其如此，因为虽然您的应用程序可以在具有小型测试数据集的台式计算机上正常运行，但重要的是要了解您的应用程序在投入使用后的响应速度，并且有数十万人使用它。

于 2008-09-21T17:17:46.980 回答
2

是的，我经常使用 Big-O 符号，或者更确切地说，我使用它背后的思维过程，而不是符号本身。主要是因为组织中很少有开发人员我经常理解它。我并不是要对那些人不尊重，但根据我的经验，对这些东西的了解是“区分男人和男孩”的事情之一。

我想知道这是否是那些只能得到“是”答案的问题之一？让我印象深刻的是，理解计算复杂性的那群人大致相当于认为它很重要的那群人。因此，任何可能回答“否”的人都可能不理解这个问题，因此会跳到下一个问题而不是停下来回答。只是一个想法 ;-）

于 2008-09-22T15:18:36.930 回答
1

在某些时间点，您将面临需要考虑的问题。有许多现实世界的问题需要处理大量数据......

例子是：

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

参加计算复杂性课程将帮助您分析和选择/创建对此类场景有效的算法。

相信我，像减小系数这样简单的事情，比如从 T(3n) 到 T(2n)，当“n”以天（如果不是几个月）来衡量时，会产生巨大的差异。

于 2008-09-21T17:16:28.247 回答
1

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

但是我应该说理解计算复杂性在游戏领域是极其重要的！是的，你听说过，“无用”的东西是游戏编程赖以生存的东西。

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

于 2008-09-22T15:29:01.007 回答
1

我经常使用复杂度计算，主要是因为我在地理空间领域工作，数据集非常大，例如涉及数百万甚至数十亿笛卡尔坐标的过程。一旦你开始遇到多维问题，复杂性可能是一个真正的问题，因为贪心算法在一个维度上是 O(n)，在三个维度上会突然跳到 O(n^3)，而且它不需要太多数据造成严重的瓶颈。正如我在类似的帖子中提到的，当您开始处理不同大小的复杂对象组时，您还会看到大 O 表示法变得很麻烦。复杂性的顺序也可能非常依赖于数据，对于精心设计的ad hoc算法，典型案例的性能比一般案例要好得多。

在分析器下测试您的算法以查看您的设计是否是您所取得的成果也是值得的。我发现由于所有明显的原因，通过算法调整比提高处理器速度更好地解决了大多数瓶颈。

有关一般算法及其复杂性的更多阅读，我发现Sedgewicks 的工作内容丰富且易于访问。对于空间算法，O'Rourkes关于计算几何的书非常出色。

于 2008-09-28T10:55:20.497 回答
1

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

于 2008-10-02T00:04:04.710 回答
0

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

于 2008-09-21T17:16:01.757 回答
0

是的，有一天当我不得不对一堆学生考试进行排序时，我对排序算法的了解派上了用场。我使用了归并排序（但不是快速排序或堆排序）。编程时，我只使用库提供的任何排序例程。（还没有对大量数据进行排序。）

我确实一直在编程中使用复杂性理论，主要用于决定使用哪些数据结构，但也用于决定是否或何时对事物进行排序，以及许多其他决策。

于 2008-09-21T17:28:10.170 回答
0

“是”和“不是”

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

有时关于NP 复杂性类的知识可能很有用。它可以帮助您意识到，当某些 NP 完全问题可以简化为您正在考虑的问题时，您可以停止考虑发明有效的算法。

不）我上面描述的只是复杂性理论的一小部分。因此很难说我使用它，我使用它的次要部分。

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

于 2008-09-21T17:41:40.713 回答
0

@Martin：您能否详细说明其背后的思维过程？

它可能不像坐下来为解决方案制定 Big-O 表示法那么明确，但它会产生对问题的意识 - 并引导您寻找更有效的答案并远离您可能采取的方法中的问题. 例如 O(n*n) 与更快的东西例如搜索存储在列表中的单词与存储在 trie 中的单词（人为示例）

我发现这对我将选择使用的数据结构以及我将如何处理大量记录产生了影响。

于 2008-09-22T17:23:01.967 回答