algorithm - 多项式时间算法

Question

我曾经听过下面这句话，但忘了是谁说的了:

While waiting for a (polynomial-time) algorithm to stop, don't forget that your lifetime is bounded by a polynomial, too.

有人可以提供引用吗？

我的另一个问题是:多项式时间算法很棒，但是实际使用的算法示例是什么，它需要 O(n^101)，即受多项式限制高学历？

Answer 1

好吧，我还没有看到 O(n^101)，但是通过组合其他稍微低阶的算法无意中创建高阶算法是很常见的。以我的经验，复杂性很少局限于一个变量，更多时候是用多个变量来表示，例如O(A*log(B)log(C)(D^2)*(E-F))

例如，我最近的任务是开发一个 algorithm to locate all potential sites for a pumped hydro electric power station for a given terrain model面积为 (X) x (Y) 米，由 (N) 3d 坐标组成。要求是在指定的最大水平距离(H)和最小高度差(Z)内找到一个指定的最小面积(A)的平面区域，另一个平面是指定的最小尺寸。在这种情况下，平坦度定义为必须移动以将区域平整到任意高程 (E) 的 Material 体积，以垂直间隔 (V) 进行搜索。区域定义为具有直径 (D) 的 (S) 边的多边形，搜索分辨率以米 (M) 为单位指定。蛮力的复杂性非常粗略地是这样的；

1) 线性扫描初始平面区域 = O((X/M) *(Y/M))，该区域的高度范围为 Z1 到 Z22)计算当前位置的平面度，计算单个体积O(S)，搜索体积最小的高度O(((Z2-Z1)/V)*S)3) 径向扫描靠近当前平坦区域的另一个平坦区域O(D/M)，并计算新区域的平坦度O((Z3-Z4)/V)*S)

结合这个我们得到 O((X/M)(Y/M)((Z2-Z1)/V)S(D/M)(H/M)((Z3-Z4)/V)*S) 并且显然需要更好的方法 ;)

由于需要在搜索中进行搜索，因此在这种情况下会出现复杂性。例如在地形中搜索平坦点，平坦点的定义本身需要进行不平凡的搜索，这反过来可能会导致更多的搜索。有时这是不可避免的，会导致不必要的复杂程度。

抽象通常会成为您的敌人，其中一个迭代库例程迭代地使用另一个迭代库例程，而后者又在您自己的代码中迭代使用。容器类的错误选择是这里常见的陷阱，尤其是当您遇到包含其他容器的容器时。