20131011第一次具体数学答案以及作业情况

  • 格式:docx
  • 大小:16.01 KB
  • 文档页数:2

二分查找递归算法以及其时间复杂度参考答案:
1、算法伪代码:
Bisearch(X,1,n,y)
{

m = (⌊1 + n⌋ ) / 2;
if X[m] = y then return (m);

else if y < X[m]
then Bisearch(X,1,m-1,y);

else if y > X[m]
then Bisearch(X,m+1,n,y);
}

2、时间复杂度递归方程:
当n=0,T(n) = 0;
当n=1,T(n) = 1;

当n>1,T(n) = T(⌊n/2⌋) + 1;
当n充分大时,令n为2的幂次(n被2整除)
展开T(n) = T(n/2)+1 = T(n/(2*2))+1+1
= T(n/(2*2….*2)) +1+1…..+1
= k = logn = O(logn)
作业检查情况:
1、 大多数同学都能够将二分查找的伪代码程序写出来,有些同学还很详细的写出了整个
程序,但是还是有少数同学是直接用语言描述的,下次写算法最好用伪代码。
2、 大多数同学的时间复杂度写的太简单。
3、 部分同学的作业版本是一样的,不排除有抄袭的可能。