Algorithm Design 2-1 Computational Tractability
TL; DL
brute-force searchは over the search spaceである。あらゆるパターンを試す。だからwe needed to spend time proportional only to N in finding a stable matching from among this stupendously large space of possibilities.
Stable Matching problem is like a n input instance is relatively small, the search space it defines is enormous; input dataは小さいのに検索データ領域が広くなる
Some Initial Attempts at Defining Efficiency
The first is the omission of where, and how well, we implement an algorithm.
Even bad algorithms can run quickly when applied to small test cases on extremely fast processors; even good algorithms can run slowly when they are coded sloppily.
Also, what is a “real” input instance?
We don’t know the full range of input instances that will be encountered in practice, and some input instances can be much harder than others.
Finally, this proposed definition above does not consider how well, or badly, an algorithm may scale as problem sizes grow to unexpected levels.
So what we could ask for is a concrete definition of efficiency that is platform-independent, instance-independent, and of predictive value with respect to increasing input sizes.
the Stable Matching Problem as an example:
The input has a natural “size” parameter N ; we could take this to be the total size of the representation of all preference lists, since this is what any algorithm for the problem will receive as input.
N is closely related to the other natural parameter in this problem: n, the number of men and the number of women. Since there are 2n preference lists, each of length n, we can view **N = 2n^2, suppressing more fine-grained details of how the data is represented. In considering the problem, we will seek to describe an algorithm at a high level, and then analyze its running time mathematically as a function of this input size N.
全部調べてたら時間がかかるという話。
Worst-Case Running Times and Brute-Force Search
we will focus on analyzing the worst-case running time: we will look for a bound on the largest possible running time the algorithm could have over all inputs of a given size N, and see how this scales with N.
So in general we will think about the worst-case analysis of an algorithm’s running time. But what is a reasonable analytical benchmark that can tell us whether a running-time bound is impressive or weak?
A first simple guide is by comparison with brute-force search over the search space of possible solutions.
Let’s return to the example of the Stable Matching Problem.
Even when the size of a Stable Matching input instance is relatively small, the search space it defines is enormous (there are n! possible perfect matchings between n men and n women), and we need to find a matching that is stable. The natural “brute-force” algorithm for this problem would plow through all perfect matchings by enumeration, checking each to see if it is stable.
The surprising punchline, in a sense, to our solution of the Stable Matching Problem is that we needed to spend time proportional only to N in finding a stable matching from among this stupendously large space of possibilities. This was a conclusion we reached at an analytical level. We did not implement the algorithm and try it out on sample preference lists; we reasoned about it mathematically. At the same time, our analysis indicated how the algorithm could be implemented in practice and gave fairly conclusive evidence that it would be a big improvement over exhaustive enumeration.
This will be a common theme in most of the problems we study: a compact representation, implicitly specifying a giant search space.
For most of these problems, there will be an obvious brute-force solution: try all possibilities and see if any one of them works.
Not only is this approach almost always too slow to be useful, it is an intellectual cop-out; it provides us with absolutely no insight into the structure of the problem we are studying. And so if there is a common thread in the algorithms we emphasize in this book, it would be the following alternative definition of efficiency.
Proposed Definition of Efficiency (2): An algorithm is efficient if it achieves qualitatively better worst-case performance, at an analytical level, than brute-force search.
This will turn out to be a very useful working definition for us. Algorithms that improve substantially on brute-force search nearly always contain a valuable heuristic idea that makes them work; and they tell us something about the intrinsic structure, and computational tractability, of the underlying problem itself.
Polynomial Time as a Definition of Efficiency
There are absolute constants c > 0 and d>0 so that on every input instance of size N, its running time is bounded by cNd primitive computational steps. (In other words, its running time is at most proportional to Nd.)
In any case, if this running-time bound holds, for some c and d, then we say that the algorithm has a polynomial running time, or that it is a polynomial-time algorithm. Note that any polynomial-time bound has the scaling property we’re looking for.
If the input size increases from N to 2N, the bound on the running time increases from cN^d to c(2N)^d = c · 2^dN^d, which is a slow-down by a factor of 2d.
Since d is a constant, so is 2d; of course, as one might expect, lower-degree polynomials exhibit better scaling behavior than higher-degree polynomials.
Proposed Definition of Efficiency (3): An algorithm is efficient if it has a polynomial running time.
Wouldn’t an algorithm with running time proportional to *n^*100—and hence polynomial—be hopelessly inefficient? Wouldn’t we be relatively pleased with a non-polynomial running time of *n^*1+.02(log n)?
There is a final, fundamental benefit to making our definition of efficiency so specific: it becomes negatable.
It becomes possible to express the notion that there is no efficient algorithm for a particular problem. In particular, the first of our definitions, which was tied to the specific implementation of an algorithm, turned efficiency into a moving target: as processor speeds increase, more and more algorithms fall under this notion of efficiency.
Our definition in terms of polynomial time is much more an absolute notion; it is closely connected with the idea that each problem has an intrinsic level of computational tractability: some admit efficient solutions, and others do not.