摘要
算法研究是计算机科学的核心领域之一。文中针对元素选择问题及解此问题的线性时间选择算法进行了深入研究,详细分析并论证了期望情况下与最坏情况下线性时间选择算法的时间复杂度,并对拟中位数元素选择问题进行了深层次的拓展,通过计算比较求出了线性时间下的最小复杂度因子。以期有助于该算法在相关领域的应用。
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.
出处
《电脑编程技巧与维护》
2009年第14期3-4,37,共3页
Computer Programming Skills & Maintenance
关键词
算法
时间复杂度
拟中位数
复杂度因子
algorithm
time complexity
analogical median
complexity factor
