| 二分法的一个难例 |
| |
| 引用本文： | 赖楚生,余新国. 二分法的一个难例[J]. 华中科技大学学报(自然科学版), 1990, 0(1) |
| |
| 作者姓名： | 赖楚生 余新国 |
| |
| 作者单位： | 华中理工大学计算机科学与工程系(赖楚生)，华中理工大学计算机科学与工程系(余新国) |
| |
| 摘 要： | 本文提出了O_n计数树的概念,并证明了O_n的计数树具有良好的性质。最后通过{O_n}这个实例证明了基于二分法所构造出的算法均具有指数型时间复杂度。
|
| 关 键 词： | 二分法 析取范式 复杂性 算法 NP完全问题 |
A Hard Example for the Bifurcation Method |
| |
| Lai Chusheng Yu Xinguo. A Hard Example for the Bifurcation Method[J]. JOURNAL OF HUAZHONG UNIVERSITY OF SCIENCE AND TECHNOLOGY.NATURE SCIENCE, 1990, 0(1) |
| |
| Authors: | Lai Chusheng Yu Xinguo |
| |
| Affiliation: | Lai Chusheng Yu Xinguo |
| |
| Abstract: | 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. |
| |
| Keywords: | Bifurcation method Disjunctive normal form Complexity Algorithm NP-Complete Problem |
| 本文献已被 CNKI 等数据库收录！ |
