二分法查找时间复杂度
在计算机科学中,二分查找算法,也称折半搜索算法,是一种在有序数组中查找某一特定元素的搜索算法
想要应用二分查找法,则这一堆数应有如下特性:
1、存储在数组中
2、有序排序
搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到这种搜索算法每一次比较都使搜索范围缩小一半
计算Binarysearch的时间复杂度:
int Binarysearch(int* a, int n, int x)
{
assert(a);
int begin= 0;
int end = nl;
while (begin < end)
{
int mid = begin + ((end-begin)>>1);
if (a[mid] < x)
begin = mid+1;
else if (a[mid] > x)
end=mid;
else
return mid;
}
return -1;
}
F(N)=O(log2(N))
最好情况:O(1)
最坏情况:log2(N)
使用前提要先排序
斐波那契的时间复杂度
#include<stdio.h>
//O(2^n)
//斐波那契数列到底贵写法完全一个没用的算法,因为太慢了
longlong Fib(size_t N)
{
if(N<3)
return 1;
return Fib(N -1)+ Fib(N - 2);)
}
int main()
{
printf("%11d\n",Fib(100));
return 0;
}