软件导刊
軟件導刊
연건도간
SOFT WARE GUIDE
2011年
11期
63-65
,共3页
叶三星%高伟%古富强%李维良
葉三星%高偉%古富彊%李維良
협삼성%고위%고부강%리유량
拉格朗日插值%动态预测%改进算法%一元高次方程实数解
拉格朗日插值%動態預測%改進算法%一元高次方程實數解
랍격랑일삽치%동태예측%개진산법%일원고차방정실수해
针对二分法的不足,提出了一种基于拉格朗日插值的动态预测查找算法,并将该算法和二分法结合得到改进的插值预测查找算法.改进算法在最坏的情况下,在含有n个元素的有序数列中,查找一个元素的最大循环比较次数为1到[log2 n]+1之间,优于二分查找的[log2 n]+1,最后从理论上证明了这一结论,并在求解一元高次方程实数解的应用中验证了这一结论.
針對二分法的不足,提齣瞭一種基于拉格朗日插值的動態預測查找算法,併將該算法和二分法結閤得到改進的插值預測查找算法.改進算法在最壞的情況下,在含有n箇元素的有序數列中,查找一箇元素的最大循環比較次數為1到[log2 n]+1之間,優于二分查找的[log2 n]+1,最後從理論上證明瞭這一結論,併在求解一元高次方程實數解的應用中驗證瞭這一結論.
침대이분법적불족,제출료일충기우랍격랑일삽치적동태예측사조산법,병장해산법화이분법결합득도개진적삽치예측사조산법.개진산법재최배적정황하,재함유n개원소적유서수렬중,사조일개원소적최대순배비교차수위1도[log2 n]+1지간,우우이분사조적[log2 n]+1,최후종이론상증명료저일결론,병재구해일원고차방정실수해적응용중험증료저일결론.
