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

摘要：

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

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

所属期刊栏目：40

分类号：TP301.5(计算技术、计算机技术)

在线出版日期：2014-04-16（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：238-241