回 帖 发 新 帖 刷新版面

主题:请教:关于频度的问题。

有下面一段代码:
      int i,j,k,dt,n;
        for( i=1;i<=n;i++){
                 for( j=1;j<=i;j++){
                        for( k=1;k<=j:k++)
                       dt+=2;      //求此行的执行频度;
           }}}
    我的结果是:
               (1)+(1+2)+(1+2+3)+(1+2+3+4)+****+(1+2+3+4+***+n);
总感觉不对。
请指正,谢了,先。

回复列表 (共1个回复)

沙发

应该没错,我化简的结果是(n^3)/6-(n^2)/2+n/3
(1)+(1+2)+(1+2+3)+(1+2+3+4)+......+(1+2+3+4+......+n)
=n*1+(n-1)*2+(n-2)*3+......+(n-(n-2))*(n-1)+(n-(n-1))*n
=n+2*n+3*n+......n*n-(1*2+2*3+......+(n-1)*n)
=n*(1+2+3+......+n)-(1*(1+1)+2*(2+1)+......+(n-1)*(n-1+1))
=n*(n*(n+1)/2)-(1*1+2*2+3*3+......+(n-1)*(n-1)+1+2+3+......+(n-1))
=n*(n*(n+1)/2)-((n-1)*n*(2*n-1)/6+(n-1)*n/2)
=(n^3)/6-(n^2)/2+n/3
这题根本就是求数列的题,鄙视出这题目的人,不过时间复杂度却必需得能这样算,faint。

我来回复

您尚未登录,请登录后再回复。点此登录或注册