线性时间选择算法时间复杂度深入研究  

Indepth Study to the Time Complexity of Linear Time Selection Algorithm

作　　者：王云鹏[1] 

机构地区：[1]厦门大学软件学院,厦门361005

出　　处：《电脑编程技巧与维护》2009年第14期3-4,37,共3页Computer Programming Skills & Maintenance

摘　　要：算法研究是计算机科学的核心领域之一。文中针对元素选择问题及解此问题的线性时间选择算法进行了深入研究,详细分析并论证了期望情况下与最坏情况下线性时间选择算法的时间复杂度,并对拟中位数元素选择问题进行了深层次的拓展,通过计算比较求出了线性时间下的最小复杂度因子。以期有助于该算法在相关领域的应用。The algorithm study is one of core fields in computer science.The paper makes a further study of element selection problem and the linear time selection algorithm which is used to solve the problem above.Moreover, it analyzes the time complexity of linear time selection algorithm respectively in the expected and worst circumstance in detail and simultaneous- ly gives it a strict proof .At last,The paper extends the method of analogical median deeply in solving the element selection problem.After caculation and comparison,the smallest complexity factor with linear time has been found out.Hope it be helpful to the application in the relevant fields.

关 键 词：算法 时间复杂度 拟中位数 复杂度因子 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] TP3[自动化与计算机技术—计算机科学与技术]