多项式时间算法

Question

我听到下面的报价一次，却忘了人，这是由于：

在等待（多项式时间）算法停下来，不要忘记，你的寿命为界也是一个多项式。

有人可以提供参考吗？

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

Answer 1

嗯，我还没有看到O（n^101），但是通常会通过组合其他稍低阶的算法而无意中创建高阶算法。根据我的经验，复杂性很少局限于一个变量，而是更多地用多个变量来表示，例如， O（A *日志（B）日志（C）（d^2）*（EF））

作为一个例子，我最近任务是开发具有通过的（X）区一个algorithm to locate all potential sites for a pumped hydro electric power station for a given terrain model（Y ）米由（N）3d坐标组成。要求在特定的最大水平距离（H）内找到指定最小面积（A）的平坦区域，并且另一个平面的最小高度差（Z）具有指定的最小尺寸。在这种情况下的平坦度被定义为必须被移动以将区域平整到任意高程（E）的材料的体积，在垂直间隔（V）处被搜索。区域被定义为直径（D）的（S）边的多边形，搜索分辨率以米（M）为单位。蛮力的复杂程度大致如此; 2）计算当前位置的平面度，计算单个的平面度，计算单个的平面度（（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）并且明显需要更好的方法;）

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

抽象往往可以成为你的敌人，其中一个迭代库例程迭代地使用另一个迭代库例程，而这个迭代库例程又在你自己的代码中迭代使用。容器类的错误选择在这里是一个常见的陷阱，特别是当你打包含其他容器的容器时。

Answer 2

最有可能的复杂度为O的任何算法（N ）是不不切实际的，这就解释了为什么这种算法没有在实践中使用。

高多项式算法问题的一个循环系列是，如果有大量对象集合（N个对象），并且需要根据给定的任意度量标准从集合中找到k个元素的“最佳”子集，或者查找具有某个属性的k个元素的子集。唯一总是适用的解决方案是枚举所有可能的子集。这立即导致O（N是固定的）复杂性（N ^k）。然而，k = 100的情况很难想象，并且在实践中对于大多数N值都不能解决。