您是否在现实生活中应用了计算复杂性理论？ [英] Did you apply computational complexity theory in real life?

问题描述

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

I'm taking a course in computational complexity and have so far had an impression that it won't be of much help to a developer.

我可能是错的，但是如果您以前走过这条路，能否请您举例说明复杂性理论如何为您提供帮助？

I might be wrong but if you have gone down this path before, could you please provide an example of how the complexity theory helped you in your work? Tons of thanks.

推荐答案

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

O(1): Plain code without loops. Just flows through. Lookups in a lookup table are O(1), too.

O（log（n））：高效优化的算法。示例：二叉树算法和二叉搜索。通常不会受伤。

O(log(n)): efficiently optimized algorithms. Example: binary tree algorithms and binary search. Usually doesn't hurt. You're lucky if you have such an algorithm at hand.

O（n）：对数据进行一次循环，很幸运。

O(n): a single loop over data. Hurts for very large n.

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

O(n*log(n)): an algorithm that does some sort of divide and conquer strategy. Hurts for large n. Typical example: merge sort

O（n * n）：某种嵌套循环。即使是小n也会受伤。与朴素矩阵计算通用。

O(n*n): a nested loop of some sort. Hurts even with small n. Common with naive matrix calculations. You want to avoid this sort of algorithm if you can.

O（n ^ x for x> 2）：一种带有多个嵌套循环的邪恶构造。很小的伤害

O(n^x for x>2): a wicked construction with multiple nested loops. Hurts for very small n.

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

O(x^n, n! and worse): freaky (and often recursive) algorithms you don't want to have in production code except in very controlled cases, for very small n and if there really is no better alternative. Computation time may explode with n=n+1.

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

Moving your algorithm down from a higher complexity class can make your algorithm fly. Think of Fourier transformation which has an O(n*n) algorithm that was unusable with 1960s hardware except in rare cases. Then Cooley and Tukey made some clever complexity reductions by re-using already calculated values. That led to the widespread introduction of FFT into signal processing. And in the end it's also why Steve Jobs made a fortune with the iPod.

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

Simple example: Naive C programmers write this sort of loop:

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）。 乔尔也写过这本书。

That's an O(n*n) algorithm because of the implementation of strlen(). Nesting loops leads to multiplication of complexities inside the big-O. O(n) inside O(n) gives O(n*n). O(n^3) inside O(n) gives O(n^4). In the example, precalculating the string length will immediately turn the loop into O(n). Joel has also written about this.

但是，复杂度类并不是全部。您必须注意n的大小。如果由于重做而使（现在的线性）指令数量大量增加，则将O（n * log（n））算法重做为O（n）不会有帮助。而且，即使n很小，优化也不会带来太大的帮助。

Yet the complexity class is not everything. You have to keep an eye on the size of n. Reworking an O(n*log(n)) algorithm to O(n) won't help if the number of (now linear) instructions grows massively due to the reworking. And if n is small anyway, optimizing won't give much bang, too.

这篇关于您是否在现实生活中应用了计算复杂性理论？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！