记录“计算某for循环结构的时间复杂度”

for(int i = 0; i < n; i++)
    for(int j = 0; j < i; j++)
        for(int k = 0; k < j; k++)
            ... 语句 ...

0   +   1   +   2   +   3   +   ...   +   n-2   +   n-1   =   n(n-1)/2

i :      0                1                   2                  3
j :      0                0  1(跳)            0 1 2(跳)          0 1 2 3(跳)
count:   0                0                   0+1                0+1+2       0+1+2+3     0+1+2+3+4 ... 0 1 2 3 4...(n-3)   0 1 2 3 4 ... (n-2)
(n-n)(n-(n+1))/2  +  (n-(n-1))(n-n)/2  +  (n-(n-2))(n-(n-1))/2  + ..................................... +  (n-2)(n-3)/2  +  (n-1)(n-2)/2



1
1 2
1 2 3
1 2 3 4
1 2 3 4 5
1 2 3 4 5 6
.
.
.
1 2 3 4 5 6 ... n-2
1 2 3 4 5 6 ... n-2 n-1
1 2 3 4 5 6 ... n-2 n-1 n

{--------------------------------n/2--------------------------------}
n + 2(n-1) + 3(n-2) + 4(n-3) + 5(n- 4) + 6(n-5) + ... + (n/2)*(n/2+1)    {if (n = 2k)}

{--------------------------------(n+1)/2----------------------------------}
n + 2(n-1) + 3(n-2) + 4(n-3) + 5(n- 4) + 6(n-5) + ... + ((n+1)/2)*((n+1)/2)    {if (n = 2k+1)}



1*1+2*2+3*3+...+(n-1)(n-1)+n*n                                                                                      2n+1
                 1                          5                        5                                              1+5+5
                2 2                        5 4                      4 5                                        2+5+4    2+4+5
               3 3 3                      5 4 3                    3 4 5                                   3+5+3    3+4+4    3+3+5
              4 4 4 4                    5 4 3 2                  2 3 4 5                             4+5+2    4+4+3    4+3+4    4+2+5 
             5 5 5 5 5                  5 4 3 2 1                1 2 3 4 5                        5+5+1    5+4+2    5+3+3    5+2+4    5+1+5
                 r                          r                        r                                        (n*(n+1)/2)*(2n+1)
                                                       3r = n(n+1)(2n+1)/2  -->  r = n(n+1)(2n+1)/6


n+2(n-1)+3(n-2)+...+(n-1)2+n*1                                                                                       n+2
                 5                          1                        1                                              5+1+1
                4 4                        1 2                      2 1                                        4+1+2    4+2+1
               3 3 3                      1 2 3                    3 2 1                                   3+1+3    3+2+2    3+3+1
              2 2 2 2                    1 2 3 4                  4 3 2 1                             2+1+4    2+2+3    2+3+2    2+4+1
             1 1 1 1 1                  1 2 3 4 5                5 4 3 2 1                        1+1+5    1+2+4    1+3+3    1+4+2    1+5+1
                 r                          r                        r                                        (n*(n+1)/2)*(n+2)
                                                         3r = n(n+1)(n+2)/2  -->  r = n(n+1)(n+2)/6

T(n) = (n-2)(n-1)n/6 = O(n^3)

颇为神奇的方法:可将数值排列为想象的正三角形,设一个正三角内的所有值的和为 r。旋转两次(每次顺时针或逆时针旋转120度,这里是顺时针旋转)使此正三角的每个角都竖直向上。依次将这样排列好的正三角内的所有对应位置的值相加,而后得到的每个位置的值将相等,且等于一个关于 n 的函数的值。最终发现等差数列之和个相同的关于 n 的函数的值,十分便于计算。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容