求大佬给下面代码求个时间复杂度
该代码是折半查找的算法 ， 实在是不懂怎么求时间复杂度，还望各位指点一二，在下感激不尽int bisearch(int ary[], int n, int key)
{
int seek_val;
int front_val = 0; //1 次
int rear_val = n- 1; //1 次
while (front_val <= rear_val)
{
seek_val = (front_val + rear_val) / 2;
if (ary == key)
{
return seek_val;
}
if (ary > key)
{
rear_val = seek_val - 1;
}
else
{
front_val = seek_val + 1;
}
}
return -1;
} 本帖最后由 迷雾少年 于 2019-8-15 23:34 编辑
序列:{1,2,3,4,5,6,7,8......n}
个数:n
第一次查找,没找到:剩余n/2;
第二次查找,没找到:剩余n/4;
第三次查找,没找到:剩余n/8;
第四次查找,没找到:剩余n/16;
...
第k次查找,没找到,剩余n/(2^k);
最差的情况在例子里就找1或者n,假如在第k次找的时候就剩下1这个数(就剩余一个)了,那么n/(2^k) = 1;
两边同乘2^k:2^k = n;
同取对数 :k = log2(n); 在array 已经排序好的情况下，binary search 的时间复杂度是logn Seawolf 发表于 2019-8-15 23:22
在array 已经排序好的情况下，binary search 的时间复杂度是logn
数组已经是排好序的
能否向这样说明一下
int s=0,i； // 1次
for(i=0；i<n；i++) // n次 (严格说为n+1次）
s=s+a； // n次
printf(“%d”,s)； // 1次
O（n）
void sum(int m,int n)
{
int i,j,s=0； // 1次
for(i=1；i<=m；i++) // m次 (m+1)
{
for(j=1；j<=n；j++) // m*n次 (m*(n+1))
{
s++； // m*n次
}
printf(“%d”,s)； // m次
}
}
O(n ^ 2)
主要是的写详细 我叫MD 发表于 2019-8-15 23:34
数组已经是排好序的
能否向这样说明一下
不是所有的东西都可以这样来写，因为在while loop里面，取值范围是一直在变化的，而且变化的规律是下一次是上一次的1/2，其他的操作近似于常数，相当于T(n) = T(n/2)+O(1)这种递推关系，用数学归纳法证明以后，就可以得到T(n) = log(n), 证明如下：
页:
[1]