设为首页 加入收藏

TOP

算法时间复杂度的计算(十二)
2013-11-20 14:18:52 来源: 作者: 【 】 浏览:1763
Tags:算法 时间 复杂度 计算


    解: 语句1的频度是1,
    设语句2的频度是t,  则:nt<=n;  t<=log2n
    考虑最坏情况,取最大值t=log2n,
    T(n) = 1 + log2n
    f(n) = log2n
    lim(T(n)/f(n)) = 1/log2n + 1 = 1
    T(n) = O(log2n)
    O(n3)
    for(i=0;i<n;i++)
    {
    for(j=0;j<i;j++)
    {
    for(k=0;k<j;k++)
    x=x+2;
    }
    }
    解:当i=m, j=k的时候,内层循环的次数为k当i=m时, j 可以取 0,1,…,m-1 ,  所以这里最内循环共进行了0+1+…+m-1=(m-1)m/2次所以,i从0取到n, 则循环共进行了: 0+(1-1)*1/2+…+(n-1)n/2=n(n+1)(n-1)/2次
    T(n) = n(n+1)(n-1)/2 = (n3-n)/2
    f(n) = n3
    所以时间复杂度为O(n3)。

        

首页 上一页 9 10 11 12 13 14 15 下一页 尾页 12/21/21
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇求二叉树两结点最小公共祖先 下一篇C语言指针类型、指针大小

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容: