算法时间复杂度的计算 - c语言编程

    解：语句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）。

算法时间复杂度的计算(三)