二分查找算法与随机二分查找算法的时间复杂度研究
关键词 二分查找，随机二分查找，时间复杂度
毕业论文设计说明书（论文）外文摘要
Title Study on the Time Complexity of Binary Search Algorithm and Random Binary Search Algorithm
Abstract
The traditional approach to analyze the algorithm complexity is to compute the average complexity of the algorithm. Although this approach has more theoretical significance, but it only gets the order of the time complexity, resulting in the difficulty of carefully comparing the algorithms with the same time complexity order. Comparatively, the experimental method turn to calculate the absolute running time, although this method has significant value for practical engineering problems, unfortunately, it can not throw more light on the theoretical analysis. In our study, we creatively combine these two methods together. Use the theoretical analysis to derive or estimate the order of the time complexity of the algorithm, then through the simulation to verify the theoretical analysis results under the help of numerical computation, function fitting and comparative analysis. In this manner, we intensively study the time complexity of both binary search algorithm and random binary search algorithm and obtain some significant conclusions. The significance of doing so has two folds: 1) provide technical support for the course teaching, 2) provide technical support for the real-world engineering applications.
Keywords Binary search, Random Binary Search, Time Complexity
目 次
1 引言 1
2 算法简介及时间复杂度分析 2
2．1 经典二分查找算法 2
2．2 随机二分查找算法 5
3 研究目标及算法设计 9
3．1 编程语言与计算平台 9
3．2 研究目标 9
3．3 算法结构设计 10
4 研究内容及结果分析 12
4．1 算法编程 12
4．2 经典二分查找算法研究 12
4．3 随机二分查找算法研究 23
4．4 经典二分查找与随机二分查找的对比 27
4．5 小结与讨论 29
结 论 31
致 谢 32
参考文献33
1 引言
二分查找算法是任何一个算法学者在其研习过程中都会遇到的算法，甚至于在某一种编程语言的学习过程中，也是经常拿二分查找算法进行举例。那么，这是不是意着二分查找算法很简单呢？我们对于二分查找算法的探索是否已经划上了句号呢？在我看来，答案当然是否定的。据目前我所了解的算法，如果将它们的时间复杂度按优劣排序出来，差不多为：