计算机科学 ›› 2013, Vol. 40 ›› Issue (Z11): 238-241.
周毅敏,李光耀
ZHOU Yi-min and LI Guang-yao
摘要: 计算机算法是电子计算机诞生时同时出现的产物。有时甚至认为算法比现代计算机出现得更早。为解决具体问题,出现了各种各样的算法。算法的时间复杂度是算法实现中最关心的问题之一。然而,面对一个问题,是否存在一个算法复杂度不可逾越的界限以及如何确定这个界限却不常作为一个值得研究的问题受到重视。针对这个问题,提出了一个基于决策树和信息论的分析方法来对一些经典算法建模并分析这些算法的时间复杂度可能达到的下界是什么,以及如何计算这个下界等。所提计算方法是真实可行的,对列出的一些经典算法是有效的,并能够应用到其它一些文中未列出的算法中。
[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! |
|