我曾经听过以下引用语，但忘记了它是由谁发表的：
在等待（多项式时间）算法停止时，请不要忘记您的寿命也被多项式所限制。
有人能提供参考资料吗？
我还有一个问题：多项式时间算法很棒，但有没有实际使用的算法需要 O(n^101)，即受高次多项式限制的算法呢？
多项式时间算法
3
- Hans
1
2个回答
2
嗯，我没有见过O(n^101)，但是通过组合其他略低阶的算法不经意地创建高阶算法是很常见的。根据我的经验，复杂度很少限于一个变量，更常见的是用多个变量来表述，例如O(A*log(B)log(C)(D^2)*(E-F))。
作为一个例子，最近我受到任务开发一个算法，用于在给定面积为(X)乘(Y)米、由(N)个三维坐标组成的地形模型中定位所有泵送水电站的潜在站点。要求是在指定的最大水平距离(H)和最小高度差(Z)内找到一个指定最小面积(A)的平坦区域，该平坦区域与另一个指定最小尺寸的平坦区域相邻。在这种情况下，平坦性被定义为必须移动的材料体积，以将该区域调平至任意高程(E)，并在垂直间隔(V)处进行搜索。区域被定义为具有(S)边和直径(D)的多边形，并且搜索分辨率以米(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)，并明显需要更好的方法 ;)
这种复杂性是由于必须在搜索中搜索而产生的。例如，在地形中搜索平坦点，其中平坦点的定义本身需要非平凡的搜索，这反过来可能导致更多的搜索。有时这是不可避免的，导致不希望的复杂度水平。
抽象常常是你的敌人，其中一个迭代库例程迭代使用另一个迭代库例程，而后者又迭代地在你自己的代码中使用。在这里，容器类的错误选择是一个常见的陷阱，特别是当你遇到包含其他容器的容器时。
作为一个例子，最近我受到任务开发一个算法，用于在给定面积为(X)乘(Y)米、由(N)个三维坐标组成的地形模型中定位所有泵送水电站的潜在站点。要求是在指定的最大水平距离(H)和最小高度差(Z)内找到一个指定最小面积(A)的平坦区域，该平坦区域与另一个指定最小尺寸的平坦区域相邻。在这种情况下，平坦性被定义为必须移动的材料体积，以将该区域调平至任意高程(E)，并在垂直间隔(V)处进行搜索。区域被定义为具有(S)边和直径(D)的多边形，并且搜索分辨率以米(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)，并明显需要更好的方法 ;)
这种复杂性是由于必须在搜索中搜索而产生的。例如，在地形中搜索平坦点，其中平坦点的定义本身需要非平凡的搜索，这反过来可能导致更多的搜索。有时这是不可避免的，导致不希望的复杂度水平。
抽象常常是你的敌人，其中一个迭代库例程迭代使用另一个迭代库例程，而后者又迭代地在你自己的代码中使用。在这里，容器类的错误选择是一个常见的陷阱，特别是当你遇到包含其他容器的容器时。
- SmacL
2
很可能任何O(n100)复杂度的算法都不实用，这也解释了为什么这样的算法在实践中不会被使用。
一类经常出现的高多项式算法问题是，当你有一个大量对象（N个对象）并且需要根据给定的任意度量找到集合中k个元素的“最佳”子集，或者找到具有某种属性的k个元素的子集。唯一总是适用的解决方案是枚举所有可能的子集。这立即导致O(Nk)的复杂度（其中k是固定的）。但是，对于大多数N的值而言，k=100的情况很难想象，因此无法在实践中解决。
- Antti Huima
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
>（就像我即将编辑的那样） - AakashM