A New Technique for Computational Complexity Analysis

摘要：

It is generally difficult to estimate tight lower bounds for many problems and algorithms. Traditionally, lower bounds are obtained either by reduction or by a direct analysis. In this paper, a new idea is presented for estimating the lower bounds of problems and algorithms. In conjunction with two algorithm design paradigms divide and conquer and incremental construction, we can derive good lower bounds from the lower bounds of the corresponding sub-problems.

关键词： Algorithm Computational Complexity Lower Bounds

作者: Xiaodong Wang Yingjie Wu

作者单位: College of Mathematics and Computer Science Quanzhou Normal University Quanzhou 362000, PR China College of Mathematics and Computer Science Fuzhou University Fuzhou 350002, PR China

会议类型: 国际会议

会议名称: 2010 International Conference on Information,Networking and Automation(2010 IEEE信息网络与自动化国际会议 ICINA 2010)

会议地点: 昆明

会议语种:英文

页码: 377-381

在线出版日期: 2010-10-17（万方平台首次上网日期，不代表论文的发表时间）