algorithm - 多项式时间算法

Question

曾经听过下面一段话，但忘记了是谁写的：

在等待（多项式时间）算法停止时，不要忘记您的生命周期也受到多项式的限制。

有人可以提供参考吗？

我的另一个问题是：多项式时间算法很棒，但是在实践中使用的算法的一个例子是什么，它需要O(n^101)，即受一个高次多项式的限制？

Answer 1

很可能任何复杂度为 O(n ¹⁰⁰ ) 的算法根本不实用，这解释了为什么在实践中不使用此类算法。

一个反复出现的高多项式算法问题是，如果您有大量对象（N 个对象），并且您需要根据给定的任意度量从集合中找到 k 个元素的“最佳”子集，或者找到一个具有特定属性的 k 个元素的子集。唯一始终适用的解决方案是枚举所有可能的子集。这会立即导致 O(N ^k ) 复杂度（其中 k 是固定的）。然而，对于大多数 N 值，k=100 的情况很难想象并且在实践中无法解决。

Answer 2

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

例如，我最近的任务是开发一种算法，用于为给定的地形模型定位抽水发电站的所有潜在站点，该地形模型的面积为 (X) x (Y) 米，由 (N) 3d 坐标组成。要求是在指定的最大水平距离 (H) 内找到指定最小面积 (A) 的平坦区域，并且另一个平坦的最小高度差 (Z) 具有指定的最小尺寸。在这种情况下，平整度被定义为必须移动以将该区域平整到任意标高 (E) 的材料体积，以垂直间隔 (V) 进行搜索。区域被定义为具有直径 (D) 的 (S) 边的多边形，搜索分辨率以米 (M) 为单位指定。蛮力的复杂性大致是这样的；

1) 线性扫描初始平面区域 = O((X/M) *(Y/M))，该区域的高度范围为 Z1 到 Z2 2) 计算当前位置的平面度，计算单个体积 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) 和一个显然需要更好的方法；）

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

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