摘要传统的复杂度分析方法是采用求期望平均的方法分析算法的平均复杂度，虽然这种分析方法具有更多的理论指导意义，但往往只能得到时间复杂度函数的阶，不便于细致地比较时间复杂度同阶的算法。而实验方法是计算比较算法的绝对运行时间，这种方法虽然对实际工程问题具有显著的应用价值，但遗憾的是对理论分析却不具有指导意义。对于本课题中的二分查找算法，我们创造性地将上述的理论分析方法和实验方法的优点结合起来，利用数学理论分析的方法，得出或估计出二分查找算法时间复杂度的阶的精确表示，然后通过数值仿真计算的方法，通过大量的实例计算、阶函数拟合与比较分析的方法，验证理论分析出的阶函数。我们深入细致地研究了二分查找算法与随机二分查找算法在各种情况下的时间复杂度，并进行了比较研究，得出了一些有意义的结论。这不仅为关于二分查找的理论教学提供了有力的依据，也为使用到了二分查找的工程计算提供了一定的借鉴作用。21118
关键词  二分查找，随机二分查找，时间复杂度
毕业论文设计说明书（论文）外文摘要
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  引言
二分查找算法是任何一个算法学者在其研习过程中都会遇到的算法，甚至于在某一种编程语言的学习过程中，也是经常拿二分查找算法进行举例。那么，这是不是意着二分查找算法很简单呢？我们对于二分查找算法的探索是否已经划上了句号呢？在我看来，答案当然是否定的。据目前我所了解的算法，如果将它们的时间复杂度按优劣排序出来，差不多为： 二分查找算法与随机二分查找算法的时间复杂度研究:http://www.youerw.com/jisuanji/lunwen_13191.html