[已解决]求大佬给下面代码求个时间复杂度

我叫MD

该代码是折半查找的算法 ， 实在是不懂怎么求时间复杂度，还望各位指点一二，在下感激不尽

1. int bisearch(int ary[], int n, int key)
   
2. {
   
3.     int seek_val;
   
4.         int front_val = 0;                                 //1 次
   
5.     int rear_val = n- 1;                               //1 次
   
6. 
   
7.         while (front_val <= rear_val)
   
8.         {
   
9.                 seek_val = (front_val + rear_val) / 2;
   
10.                 if (ary[seek_val] == key)
    
11.                 {
    
12.                         return seek_val;
    
13.                 }
    
14.                 if (ary[seek_val] > key)
    
15.                 {
    
16.                         rear_val = seek_val - 1;
    
17.                 }
    
18.                 else
    
19.                 {
    
20.                         front_val = seek_val + 1;
    
21.                 }
    
22.         }
    
23. 
    
24.         return -1;
    
25. }

复制代码

最佳答案

月排行榜 / 总排行榜

迷雾少年

2019-8-15 23:07:14

序列:{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);

跳转到最佳答案楼层

迷雾少年

序列:{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);

Seawolf

在array 已经排序好的情况下，binary search 的时间复杂度是logn

我叫MD

Seawolf 发表于 2019-8-15 23:22
在array 已经排序好的情况下，binary search 的时间复杂度是logn

数组已经是排好序的
能否向这样说明一下

1.     int s=0,i；          // 1次
   
2.     for(i=0；i<n；i++)   // n次 (严格说为n+1次）
   
3.     s=s+a[i]；           // n次
   
4.     printf(“%d”,s)；     // 1次

复制代码

O（n）

1. void sum(int m,int n)
   
2. {
   
3.     int i,j,s=0；              // 1次
   
4.     for(i=1；i<=m；i++)        // m次 (m+1)
   
5.     {
   
6.         for(j=1；j<=n；j++)    // m*n次 (m*(n+1))
   
7.         {
   
8.             s++；              // m*n次
   
9.         }
   
10.         printf(“%d”,s)；       // m次
    
11. 
    
12.     }
    
13. }

复制代码

O(n ^ 2)


主要是的写详细

Seawolf

我叫MD 发表于 2019-8-15 23:34
数组已经是排好序的
能否向这样说明一下

不是所有的东西都可以这样来写，因为在while loop里面，取值范围是一直在变化的，而且变化的规律是下一次是上一次的1/2，其他的操作近似于常数，相当于T(n) = T(n/2)+O(1)这种递推关系，用数学归纳法证明以后，就可以得到T(n) = log(n), 证明如下：