鱼C论坛

 找回密码
 立即注册
查看: 3136|回复: 4

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

[复制链接]
发表于 2019-8-15 23:07:13 | 显示全部楼层 |阅读模式
10鱼币
该代码是折半查找的算法 , 实在是不懂怎么求时间复杂度,还望各位指点一二,在下感激不尽
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
本帖最后由 迷雾少年 于 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);

最佳答案

查看完整内容

序列:{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);
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2019-8-15 23:07:14 | 显示全部楼层    本楼为最佳答案   
本帖最后由 迷雾少年 于 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);
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2019-8-15 23:22:36 | 显示全部楼层
在array 已经排序好的情况下,binary search 的时间复杂度是logn
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2019-8-15 23:34:24 | 显示全部楼层
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)


主要是的写详细
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2019-8-16 01:09:13 | 显示全部楼层
我叫MD 发表于 2019-8-15 23:34
数组已经是排好序的
能否向这样说明一下

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

12.jpg
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-23 18:27

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表