你有没有适用计算的复杂性理论，在真正的生活？

StackOverflow https://stackoverflow.com/questions/111426

  •  02-07-2019
  •  | 
  •  

题

我把一个课程计算的复杂性和迄今为止，有一个印象，即它不会有多大帮助一个开发商。

我可能是错的但是如果你已经走上这条道路之前，你能不能请提供如何复杂的理论帮助你在你的工作吗？吨的感谢。

有帮助吗？

解决方案

O（1）：没有循环的普通代码。刚流过。查找表中的查找也是O（1）。

O（log（n））：有效优化的算法。示例：二叉树算法和二进制搜索。通常不会受伤。如果你有这样的算法，你很幸运。

O（n）：数据上的单个循环。非常大的伤害。

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

O（n * n）：某种嵌套循环。即使是小n也会受伤。与天真矩阵计算相同。如果可以的话，你想避免使用这种算法。

O（对于x> 2，n ^ x）：具有多个嵌套循环的邪恶构造。伤害很小的n。

O（x ^ n，n！和更糟）：你不希望在生产代码中使用的怪异（通常是递归）算法，除非在非常受控的情况下，对于非常小的n，如果没有更好的替代方案。计算时间可能会爆炸，n = n + 1。

从更高复杂度的类中移动算法可以使您的算法飞行。考虑傅立叶变换，其具有O（n * n）算法，除了极少数情况外，该算法在20世纪60年代的硬件中无法使用。然后Cooley和Tukey通过重新使用已计算的值来减少复杂性。这导致FFT广泛应用于信号处理。最后，这也是史蒂夫·乔布斯为iPod赚大钱的原因。

简单的例子：Naive 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很小，那么优化也不会产生太大的影响。

其他提示

虽然确实可以在没有对算法复杂性的任何理解的情况下在软件开发方面取得很大进展。我发现我一直都在使用复杂的知识;但是，在这一点上，它往往没有意识到它。学习复杂性的两件事让你作为一个软件开发人员可以比较做同样事情的非相似算法（排序算法是典型的例子，但大多数人实际上并没有编写自己的排序）。它给你的更有用的东西是一种快速描述算法的方法。

例如，考虑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），这对于大型数据库会产生巨大的差异，但对于小型数据库来说，它根本不是什么。

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

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

快速思考复杂性理论对我来说在商业数据处理，GIS，图形编程和理解算法中一直很重要。这是CS研究中最有用的课程之一，与你通常自学的方法相比。

计算机是不明智的，他们将会做任何你指示他们做的。编译器可以优化码一个位给你，但他们不能优化算法。人类大脑的工作方式不同，这就是为什么你需要了解的大O.考虑计算的斐波那契数字。我们都知道F(n)=F(n-1)+F(n-2)，并开始与1,1你可以很容易地计算出以下数字没有很大的努力，在线性时间。但如果你告诉计算机到计算这一公式(递归)，这不是线性(至少，在必要的语言)。不知怎的，我们的大脑有优化算法，但是编译器不能做到这一点。所以，你需要 工作 在 算法 做的更好。

然后，你需要训练，发现大脑的优化，这看起来那么显而易见，要看到当代码可能是无效的，要知道的模式坏的和好的算法(在计算复杂)等。基本上，这些课程为几件事情：

  • 理解执行模式和数据的结构和产生什么影响，他们有时间你的计划需要完成；
  • 训练你的头脑，发现潜在问题的算法，当它可能是效率低下的大数据集。或者了解结果的分析；
  • 好好学习知的方法来提高算法通过减少他们的计算的复杂性；
  • 自己做好准备以通过面试在凉爽的公司)

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

在许多情况下尤其如此，因为虽然您的应用程序可以在具有较小测试数据集的台式计算机上正常工作，但了解应用程序在您使用它后的响应速度非常重要，并且有数百种成千上万的人使用它。

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

我想知道这是否是只能接受“是”的问题之一答案？令我感到震惊的是，理解计算复杂性的人群大致相当于认为重要的人群。所以，任何可能回答否的人可能都不理解这个问题，因此会跳到下一个问题，而不是停下来回应。只是一个想法; - ）

有点时候，你将面临的问题，需要考虑它们。有许多真实世界的问题，需要操纵的大量数据...

实例有：

  • 地图应用程序...如谷歌地图-你会如何处理路线数据的全球和绘制他们？你需要汲取他们快！
  • 后勤应用程序...认为旅行销售的人类固醇
  • 数据挖掘...所有大型企业的要求之一，你会怎么我一个数据库，包含100表和10+行，并提出了一个有用的结果之前的趋势，获得过时了吗？

把一课程中计算的复杂性将帮助你分析和选择/建算法，是有效对于这样的情况。

相信我，一些简单的减少系数，说T(3n)下来的T(2n)可以让一个巨大的差异时，"n"是衡量天如果不是几个月。

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

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

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

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

还需要在分析器下测试您的算法，看看您的设计是否是您所获得的。我发现大多数瓶颈都可以通过算法调整得到更好的解决，而不是提高处理器速度，原因很明显。

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

在您的日常生活中，不要靠近计算机，您应该应用复杂性和并行处理的概念。这将使您更有效率。缓存一致性。那种事。

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

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

'是'和'没有'

是）我经常使用大O-notation 开发和实现算法。 例如。当你应该处理10 ^ 3项并且第一个算法的复杂度是O（n log（n））而第二个算法的复杂度是O（n ^ 3）时，你可以说第一个算法几乎是实时的，而第二个算法则需要相当多的计算。

有时，有关 NP复杂性类的知识非常有用。它可以帮助您意识到，当一些NP完全问题可以减少到您正在考虑的问题时，您可以不再考虑发明有效的算法。

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

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

@Martin：你能详细说明它背后的思考过程吗？

它可能没那么明确，只需坐下来制定一个解决方案的Big-O表示法，但它会引发对问题的认识 - 并引导您寻找更有效的答案并远离方法中的问题你可能会。例如O（n * n）与更快的东西，例如搜索存储在列表中的单词与存储在trie中的单词（设想示例）

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

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

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top