摘要
本文提出了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.
出处
《华中理工大学学报》
CSCD
北大核心
1990年第1期81-86,共6页
Journal of Huazhong University of Science and Technology
基金
国家自然科学基金
关键词
二分法
算法
复杂度
NP完全问题
Bifurcation method
Disjunctive normal form
Complexity
Algorithm
NP-Complete Problem