- 上一篇：ASP.net大学生个人学习生活管理软件的开发
- 下一篇：JSP图书馆座位管理系统设计+文献综述
2 算法简介及时间复杂度分析
2．1 经典二分查找算法
将一个给定的元素x与一个已排序数组A[low…high]的中间元素做比较，如果x < A[mid]，这里mid = floor((low+high)/2)，则不考虑A[mid…high]，而是对A[low…mid-1]重复实施相同的方法。类似地，如果x > A[mid]，则放弃A[low…mid]，并对A[mid+1…high] 重复实施相同的方法。如此，我们就可以使用递归方法来实现这一搜索算法（伪代码如下）：
输入：n个元素的升序数组A[1…n]和元素x
输出：若x=A[j], 1£j£n, 则输出j, 否则输出0
low←1; high ←n; j←0
while(low £high) and (j=0)
mid ← ë( low+high)/2û
if x=A[mid] then j ←mid
else if x<A[mid] then high ←mid-1
else low ←mid+1
end while
return j
对于上面的经典二分查找的伪代码，我们作简要分析：为了求出算法的执行时间，我们计算元素间的比较次数，因为这是一个基本运算，也就是说，算法的执行时间与完成元素间比较次数是成比例的。我们将假定每个if-else-else比较当作一次比较来计算，首先注意到当n=0时，即数组是空的，则算法不执行任何元素的比较。当n=1时，else的部分将被执行，并且若x≠A[mid]，算法将对空数组递归。从而得到当n=1时，算法刚好执行一次比较。如果n>1，则存在两种可能；当x=A[mid]时，则算法仅仅执行一次比较；否则算法所需的比较次数是1加上由递归调用数组的前或后一半所执行的比较次数。如果设C(n)表示算法对大小为n的数组在最坏的情况下所执行的比较次数，则C(n)可表示为如下的递推式：
1 若n=1
1+C( ) 若n≥2
设对某个整数k≥2,满足2 ≤n≤2 。展开上述递推式，可得到
-
基于MATLAB的图像增强算法设计
-
基于Kinect的手势跟踪与识别算法设计
-
JAVA+MYSQL《算法与数据结构...
-
神经网络算法在核素识别中的应用研究
-
人脸图像品质评估算法设计与实现
-
基于RGB-D摄像机的图像分割算法研究与实现
-
云虚拟环境下资源分配优化算法的研究
河岸冲刷和泥沙淤积的监测国内外研究现状
杂拟谷盗体内共生菌沃尔...
酸性水汽提装置总汽提塔设计+CAD图纸
大众媒体对公共政策制定的影响
java+mysql车辆管理系统的设计+源代码
十二层带中心支撑钢结构...
中考体育项目与体育教学合理结合的研究
乳业同业并购式全产业链...
当代大学生慈善意识研究+文献综述
电站锅炉暖风器设计任务书