计算机科学 ›› 2013, Vol. 40 ›› Issue (Z11): 238-241.

• 数据存储与挖掘 • 上一篇    下一篇

一种根据决策树结合信息论的经典算法复杂度可能下界分析

周毅敏,李光耀   

  1. 同济大学电信学院CAD中心 上海200080;同济大学电信学院CAD中心 上海200080
  • 出版日期:2018-11-16 发布日期:2018-11-16

Analysis of Probable Lower Bound of Time Complexity of Some Classical Algorithms Based on Decision Tree and Information Theory

ZHOU Yi-min and LI Guang-yao   

  • Online:2018-11-16 Published:2018-11-16

摘要: 计算机算法是电子计算机诞生时同时出现的产物。有时甚至认为算法比现代计算机出现得更早。为解决具体问题,出现了各种各样的算法。算法的时间复杂度是算法实现中最关心的问题之一。然而,面对一个问题,是否存在一个算法复杂度不可逾越的界限以及如何确定这个界限却不常作为一个值得研究的问题受到重视。针对这个问题,提出了一个基于决策树和信息论的分析方法来对一些经典算法建模并分析这些算法的时间复杂度可能达到的下界是什么,以及如何计算这个下界等。所提计算方法是真实可行的,对列出的一些经典算法是有效的,并能够应用到其它一些文中未列出的算法中。

关键词: 算法,时间复杂度,决策树,信息论,下界

Abstract: Algorithms are concurrently born with electronic computers.Sometimes we even believe algorithms’ birth is long before that of modern computers.Various algorithms were designed to solve miscellaneous concrete problems.Nevertheless,whether the time complexity of an algorithm’s lower bound exists and if so how to determine that lower bound do not usually come to be a problem worth researching or being valued.A method of modeling and analyzing the time complexity’s lower bound of some classical algorithms wase proposed based on decision model and information theory and how to calculate it was presented to solve the problem.The method provided is feasible and effective for the classical algorithms listed and is also applicable to those not listed we believe.

Key words: Algorithm,Time complexity,Decision tree,Information theory,Lower bound

[1] Cormen T H,Leiserson C E,Rivest R L,et al.Introduction to Algorithms(2nd Edition)[M].Massachusetts:The MIT Press,2002
[2] Garey M R.Optimal Binary Identification Procedures[J].Siam Journal on Applied Mathematics,1972,23(7):173-186
[3] Bellala1G,Bhavnani S K,Scott1C.Extensions of Generalized Binary Search to Group Identification and Exponential Costs[C]∥Advances in Neural Information Processing Systems,2010:1-9
[4] Buhrman H,de Wolf R.Complexity measures and decision tree complexity:a survey[J].Theoretical Computer Science,2002,288:21-43
[5] Prüfer H.Neuer Beweis eines Satzes über Permutationen[Z].Arch.Math.Phys.,27:742-744
[6] Kleinberg J,Tardos .Algorithm Design[Z].Boston:PearsonEducation,2006
[7] Cover T M,Thomas J A.Elements of Information Theory(2nd Edition)[M].Hoboken,New Jersey:John Wiley & Sons Inc.,2006

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!