摘要
针对二分法的不足,提出了一种基于拉格朗日插值的动态预测查找算法,并将该算法和二分法结合得到改进的插值预测查找算法。改进算法在最坏的情况下,在含有n个元素的有序数列中,查找一个元素的最大循环比较次数为1到[log2n]+1之间,优于二分查找的[log2n]+1,最后从理论上证明了这一结论,并在求解一元高次方程实数解的应用中验证了这一结论。
The binary search algorithm is not enough good,so this paper presented dynamic prediction search algorithm based on Lagrange interpolation,and it combined the algorithm and binary search algorithm and presented an improved interpolation prediction algorithm based on them.In the worst case,it compared times to find an element of an array by using the improved algorithm,and it was proved to be obviously better than binary search algorithm in theory,and at last this conclusion was verified in the application of solving the real number solutions of higher degree equation.
出处
《软件导刊》
2011年第11期63-65,共3页
Software Guide
基金
国家自然科学基金项目(41002115)
关键词
拉格朗日插值
动态预测
改进算法
一元高次方程实数解
Lagrange Interpolation
Dynamic Prediction
Improved Algorithm
the Real Number Solutions of Higher Degree Equation
