计算复杂性理论在现实生活中应用了吗？
我正在学习计算复杂性的课程，迄今为止有一个印象是它对开发人员没有太大的帮助。
我可能是错的，但如果你之前走过了这条道路，能否请你举一个复杂性理论如何帮助你工作的例子？ 吨的感谢。
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）算法，该算法在20世纪60年代的硬件中不可用，除了极少数情况。 然后，Cooley和Tukey通过重新使用已经计算的值来降低复杂度。 这导致了FFT在信号处理中的广泛应用。 最后，这也是史蒂夫乔布斯为iPod创造财富的原因。
简单的例子：天真的C程序员写这样的循环：
for (int cnt=0; cnt < strlen(s) ; cnt++) {
/* some code */
}
这是一个O（n * n）算法，因为strlen（）的实现。 嵌套循环导致大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）。 没有复杂性理论，这个人就不得不解释关于表扫描等等。 如果我们为订单表添加一个索引
CREATE INDEX ORDER_USERID ON Order(UserId)
那么上面的查询可能是O（n log n），这对于大型数据库会有很大的不同，但是对于一个小型的数据库来说，这完全没有任何意义。
有人可能会争辩说，复杂性理论不需要理解数据库是如何工作的，而且它们是正确的，但是复杂性理论为思考和讨论处理数据的算法提供了一种语言。
对于大多数类型的编程工作来说，理论部分和证明本身可能并不有用，但他们正在做的是试图给你一个直觉，即能够立即说出“这个算法是O（n ^ 2），所以我们可以'运行在这100万个数据点上“。 即使在大量数据的最基本处理中，您也会遇到这种情况。
快速思考复杂性理论对于我来说在业务数据处理，GIS，图形编程和理解算法方面一直非常重要。 这是您从CS研究中获得的最有用的教训之一，与您通常自学的内容相比较。
链接地址: http://www.djcxy.com/p/39661.html上一篇: Did you apply computational complexity theory in real life?