二分法的一个难例

A Hard Example for the Bifurcation Method

本文提出了O_n计数树的概念,并证明了O_n的计数树具有良好的性质。最后通过{O_n}这个实例证明了基于二分法所构造出的算法均具有指数型时间复杂度。

The concepts of the count node and count tree are proposed. It has been proved that the number of the nodes of every count tree of On is larger than or equal to 2n-1-1, where On is the disjunctive normal form of the occupancy problem. Then it is shown that the disjunctive normal form family {On} is a hard example for the bifurcation method. This shows that algorithms based on the bifurcation method are all characterized by time complexity in the exponential form.