词条 | Prune and search |
释义 |
The basic idea of the method is a recursive procedure in which at each step the input size is reduced ("pruned") by a constant factor {{math|0 < p < 1}}. As such, it is a form of decrease and conquer algorithm, where at each step the decrease is by a constant factor. Let {{mvar|n}} be the input size, {{math|T(n)}} be the time complexity of the whole prune-and-search algorithm, and {{math|S(n)}} be the time complexity of the pruning step. Then {{math|T(n)}} obeys the following recurrence relation: This resembles the recurrence for binary search but has a larger {{math|S(n)}} term than the constant term of binary search. In prune and search algorithms S(n) is typically at least linear (since the whole input must be processed). With this assumption, the recurrence has the solution {{math|1=T(n) = O(S(n))}}. This can be seen either by applying the master theorem for divide-and-conquer recurrences or by observing that the times for the recursive subproblems decrease in a geometric series. In particular, Megiddo himself used this approach in his linear time algorithm for the linear programming problem when the dimension is fixed[2] and for the minimal enclosing sphere problem for a set of points in space.[1] References1. ^1 N. Megiddo. Linear-time algorithms for linear programming in R3 and related problems. SIAM J. Comput., 12:759–776, 1983. 2. ^Nimrod Megiddo, Linear Programming in Linear Time When the Dimension Is Fixed, 1984 2 : Geometric algorithms|Linear programming |
随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。