Polynomial Time Algorithms

Question

I once heard the following quote, but forgot who this is attributed to:

While waiting for the algorithm to stop (polynomial time), do not forget that your life time is also limited by the polynomial.

Can someone provide a link?

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

Answer 1

Well, I have not seen O (n ^ 101), but usually inadvertently create high-order algorithms by combining other algorithms of a slightly lower order. In my experience, complexity is rarely limited to one variable; it is more often stated in terms of several variables, for example. O (A * journal (B), journal (C) (D ^ 2) * (EP))

As an example, I was recently commissioned to develop an algorithm to search for all potential objects for a pumped hydroelectric power station for a given terrain model with an area of ​​(X) by (Y) meters, consisting of (N) 3d coordinates. It was required to find the flat area of ​​a given minimum area (A) within a given maximum horizontal distance (H), and the minimum height difference (Z) of another apartment has a given minimum size. A plane in this context is defined as the volume of material that would need to be moved in order to align the region to an arbitrary height (E), searching in the vertical interval (V). Areas were defined as polygons (S) of the sides with diameter (D), and search resolution was indicated in meters (M). The brute force complexity looks something like this:

1) Linearly scan the initial flat area = O ((X / M) * (Y / M)), this area will have a height range from Z1 to Z2 2) Calculate the plane in the current position, calculate a single volume O (S), search height with minimum volume O (((Z2-Z1) / V) * S) 3) Radially scan another flat area near the current flat area O (D / M) and calculate the flatness of the new area O ((Z3-Z4) / V) * S)

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

Complexity arises in this case because of the need to search in searches. for example, searching for flat spots in an area where the definition of flat spots itself requires a nontrivial search, which, in turn, can lead to a larger search. This is sometimes inevitable, leading to undesirable levels of difficulty.

Abstraction can often be your enemy here, where one iterative library procedure iteratively uses another iterative library procedure, which in turn is used iteratively in your own code. A poor selection of container classes is a common trap here, especially when you click on containers containing other containers.

Answer 2

Most likely, any algorithm of complexity O (n ¹⁰⁰ ) is not entirely practical, which explains why such algorithms are not used in practice.

One repeating family of algorithms with a high polynomial algorithm is that where you have a large collection of objects (N objects) and you need to find the "optimal" subset of k elements from the collection according to this arbitrary metric or find a subset of k elements with a specific property. The only solution that is always applicable is to list all possible subsets. This immediately leads to complexity O (N ^k ) (where k is fixed). However, the case with k = 100 is difficult to imagine and cannot be practically solved for most N.