您是否在现实生活中应用了计算复杂性理论？

我正在学习计算复杂性的课程,到目前为止,它给人的印象是它对开发人员没什么帮助.

我可能错了,但如果你以前走过这条道路,你能否提供一个例子,说明复杂性理论如何帮助你完成工作？非常感谢.

O(1):没有循环的普通代码.刚流过.查找表中的查找也是O(1).

O(log(n)):有效优化的算法.示例:二叉树算法和二进制搜索.通常不会受伤.如果您手头有这样的算法,那就太幸运了.

O(n):数据上的单个循环.伤害非常大的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).乔尔也写过这个.

但复杂性并不是一切.你必须留意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研究中最有用的课程之一,与您通常自学的方法相比.