二分查找算法与随机二分查找算法的时间复杂度研究(2)
O(1), O(log2 n), O(n), O(n log2 n), O(n2), O(nk)(k>2)
在众多常用算法中，就数二分查找算法的时间复杂度是 ，至于其他的大多都是 或者 。而且也正是因为有了二分查找算法的 的设计理念, 才促进了很多 的算法时间复杂度缩减到只要 ，因此，二分查找算法被应用于多个领域，所以，我们对于它的一点点细微的发现甚至于改进，都会给二分查找算法相关的领域带来重大的影响，比如各种涉及到搜索软件，我们能够根据新的发现来升级软件中的算法，在企业中，一个拥有更高性能算法的软件其价值也会相对更高，而在追求细微的学术研究中，二分查找会产生更大的影响。事实上，二分查找算法中关于“抛弃部分元素（这里是一半或接近一半元素），不断减小问题规模，加快求解进程”的思想也被研究者们借鉴，用来设计出其他优秀的算法。因此，关于二分查找的研究对于理论研究和实际应用都具有不可忽视的重要意义。所以，对于二分查找算法的更深入研究是必不可少的。
而对于随机算法，自从它被提出以来之后就受到了广泛的关注，随机算法在信息检索、分布式计算、密码学、通信等等许多领域都有涉及到。随机算法可分为三类，即蒙特卡洛型、拉斯文加斯型和舍伍德型。其中蒙特卡洛型随机算法以其“允许以较小的错误率为代价，赢得计算复杂度的大幅减少”为其特色和鲜明的亮点，在理论研究和实际应用中备受瞩目；舍伍德型随机算法的特点是通过引入随机化因素，将输入数据重新“洗牌”，尽量减少“不良”的输入实例对于算法复杂度的影响。虽然在理论上舍伍德型随机算法并不能减小算法的平均时间复杂度，但随机化“洗牌”处理能将出现最坏时间复杂度的概率尽量减小，因此，舍伍德型随机算法在实际工程计算中也是一种有力的工具。但是随机算法由于其本身的诸多限制，对于某些随机算法而言，在数学期望意义下（或者在实际工程计算中）很大程度上降低算法度的同时，由于随机算法本身的不确定性，加上算法输入的影响，给算法复杂度分析和控制带来一定程度的困难，因而在实际应用中也显示其有一定的不足。
所以，由于二分查找应用的普遍性，随机的二分查找算法也很有必要受到关注，我们需要知道随机的二分查找与经典的比较之下哪一个更优，也需要知道随机的二分查找算法是否会有所限制，导致复杂度变高。图1.1给出了随机二分查找与经典二分查找的算法过程对比，从这个个例中可以观察出，前者比后者的计算次数更多，但这是否意着：就平均时间复杂度而言，随机算法的复杂度大于经典二分查找的复杂度呢？这是个值得研究的问题。
图1.1 二分查找算法与随机二分查找算法的查找过程对比
算法的复杂度（特别是时间复杂度）分析对于理论研究和工程应用都具有重要的指导意义。传统的复杂度分析方法是采用求期望平均的方法分析算法的平均复杂度，虽然这种分析方法具有更多的理论指导意义，但往往只能得到时间复杂度函数的阶，不便于细致地比较时间复杂度同阶的算法，因而对实际工程的指导意义实在有限。众所周知，算法的时间复杂度与问题的规模和输入实例有关。与理论分析方法相比，实验方法是计算比较算法的绝对运行时间，这种方法虽然对实际工程问题具有显著的应用价值，但遗憾的是对理论分析却不具有指导意义，因为算法具体实例化为程序运行时，计算时间还跟软硬件平台甚至编程技巧有关。对于本课题中的二分查找算法，我们创造性地将上述的理论分析方法和实验方法的优点结合起来，利用数学理论分析的方法，得出或估计出二分查找算法时间复杂度的阶的精确表示，然后通过数值仿真计算的方法，通过大量的实例计算、阶函数拟合与比较分析的方法，验证理论分析出的阶函数。这不仅为关于二分查找的理论教学提供了有力的依据，也为使用到了二分查找的工程计算提供了一定的借鉴作用。