多项式时间算法 [英] Polynomial time algorithms

问题描述

我听到下面引用一次，却忘了人，这是由于：

I heard the following quote once, but forgot to whom it is attributed:

在等待（多项式时间）算法停止，不要忘记，你的一生是由一个多项式界了。

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

有人能提供一个参考？

另一个问题我已经是：多项式算法是伟大的，但在实际中使用的算法，需要为O（n ^ 101），即一个例子为界的高度多项式？

Another question I have is: Polynomial-time algorithms are great, but what is an example of an algorithm used in practice which requires O(n^101), i.e. is bounded by a polynomial of high degree?

推荐答案

嗯，我还没有看到为O（n ^ 101），但它是常见的通过结合其他稍低阶算法在不经意间创造高阶算法。在我的经验，复杂性很少限于一个变量，它更经常在多个变量，例如来表述O（A *日志（B）的日志（C）的（D ^ 2）*（E-F））

Well, I haven't seen O(n^101), but it is common to inadvertently create high order algorithms by combining other slightly lower order algorithms. In my experience, the complexity is rarely limited to one variable, it is more often stated in terms of multiple variables, e.g. O(A*log(B)log(C)(D^2)*(E-F))

作为一个例子，我最近负责开发一个<一个href="http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6V2S-4XK31PV-2&_user=10&_coverDate=01%2F31%2F2010&_rdoc=1&_fmt=high&_orig=search&_sort=d&_docanchor=&view=c&_searchStrId=1378890467&_rerunOrigin=scholar.google&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=2ec908a9da6af34c6dcbe1a43cc37cbd"相对=nofollow>算法来定位所有的潜在位点泵送水力发电站用于与（X）的一个区域中的给定的地形模型通过由（N）的三维坐标（Y）的米。的要求是要找到一个平坦区中的另一个平面的一个指定的最大水平距离（H）和最小高度差（Z）内的指定最小面积（A）的是指定的最小大小的。平坦度在此上下文中被定义为材料的体积，将有被移动到水平区域为任意高度（E）中，搜索在垂直周期（V）。区域被定义为（S）两侧直径（D）多边形，和搜索决议米（m）指定。蛮力复杂的推移很不客气地这样的事情;

As an example, I was recently tasked to develop an algorithm to locate all potential sites for a pumped hydro electric power station for a given terrain model with an area of (X) by (Y) meters made up of (N) 3d coordinates. The requirement was to find a flat area of a specified minimum area (A) within a specified maximum horizontal distance (H) and minimum height difference (Z) of another flat are of specified minimum size. Flatness in this context is defined as the volume of material that would have to be moved to level the area to an arbitrary elevation (E), searched at vertical interval (V). Areas were defined as polygons of (S) sides with diameter (D), and search resolution was specified in meters (M). The brute force complexity goes very roughly something like this;

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）

1) Linearly scan for initial flat area = O((X/M) *(Y/M)), this area will have a height range of Z1 to Z2 2) Compute flatness at current position, computing single volume O(S), search for height with minimum volume O(((Z2-Z1)/V)*S) 3) Radially scan for another flat area close to the current flat area, O(D/M), and compute the flatness of the new area O((Z3-Z4)/V)*S)

结合这一点，我们得到O（（X / M）的（Y / M）的（（Z2-Z1）/ V）的取值的（D / M）（H / M）的（（Z3-Z4）/ V）* S）和更好的方法显然需要;）

Combining this we get O((X/M)(Y/M)((Z2-Z1)/V)S(D/M)(H/M)((Z3-Z4)/V)*S) and an obvious need for better approach ;)

的复杂性出现在这种情况下，因为有必要搜索范围内进行搜索。例如搜寻在平点的地形，在这里的平点本身的定义需要一个非平凡搜索，这反过来又可能导致更多的搜索。有时，这是无法避免的，从而导致复杂的不希望的水平。

The complexity arises in this case because of the necessity to search within searches. e.g. searching for flat spots in the terrain, where the definition of flat spots itself requires a non-trivial search, which in turn may lead to more searching. Sometimes this is unavoidable, leading to undesirable levels of complexity.

抽象往往可以在这里你的敌人，其中一个迭代库程序反复使用而这又是反复用在自己的code另一种迭代的库函数。容器类错误的选择是一个普通的陷阱的，特别是当你打包含其他容器容器。

Abstraction can often be your enemy here, where one iterative library routine iteratively uses another iterative library routine which in turn is used iteratively in your own code. Bad choices of container classes are a regular pitfall here, particularly when you hit containers containing other containers.

这篇关于多项式时间算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！