一、二分查找法的时间复杂度
int Er_Feng_Find(int arr[],int sz, int data)
{
int left = 0;
int right = sz - 1;
int mid = 0;
while (left <= right)
{
mid =(right + left) / 2;
if (data < arr[mid])
{
right =mid - 1;
}
if (data > arr[mid])
{
left =mid + 1;
}
if (data == arr[mid])
{
return mid;//找到了返回下表
}
}
return -1;//找不到返回-1
}
int main()
{
int arr[10] = { 1,5,7,13,16,18,19,21,25,27 };
int data = 18;
int sz = sizeof(arr) / sizeof(arr[0]);
int pos=Er_Feng_Find(arr,sz,data);
if (pos != -1)
{
printf("找到了，下表为：%d\n", pos);
}
system("pause");
return0;
}
二分查找的过程如下： 因为没找一次，查找的范围缩小一半，如果找了x次，那么该数组的总个数N=2^x，所以x=log N,所以时复杂度为O(log N)。 因为辅助空间是常数，所以空间复杂度为O(1)
二、递归实现的斐波那契数列的时间复杂度和空间复杂度
代码如下：
int fibo(int n)
{
if(n<=2)
{
return1;
}
else
{
return fibo(n-1)+fibo(n-2);
}
}
假如求6的斐波那契数，过程如下：
时间复杂度，我们只看最坏情况，最坏情况是这个二叉树是满的，若是满的，则有2^(N-1)-1，所以时间复杂度是O(2^N)。 fib（6）的的=最深高度是5，所以空间复杂度是O(N-1)，即O(N)。
