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

我叫MD

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

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[seek_val] == key)
                {
                        return seek_val;
                }
                if (ary[seek_val] > key)
                {
                        rear_val = seek_val - 1;
                }
                else
                {
                        front_val = seek_val + 1;
                }
        }

        return -1;
}

最佳答案

月排行榜 / 总排行榜

迷雾少年

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

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

    int s=0,i；          // 1次
    for(i=0；i<n；i++)   // n次 (严格说为n+1次）
    s=s+a[i]；           // 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)


主要是的写详细

Seawolf

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

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