嵌套 for 循环波浪符号的复杂性

Complexity in tilde notation of nested for loops

如何找到以下算法的 tilde notation 的复杂度:

for (int j = 0; j < N; j++) {

    for (int k = j + 1; k < N; k++) {

        array[k] = array[j];

    }

    array[j] = k
}

如果 N = 9:

我做了一个 table 内部 for-loop 循环的次数
|     j      | # of loops  | 
|:-----------|------------:|
|     0      |      8      |          
|     1      |      7      |       
|     2      |      6      |         
|     3      |      5      |         
|     4      |      4      |     
|     5      |      3      | 
|     6      |      2      |
|     7      |      1      |
|     8      |      0      |

随着您的评估,内部迭代次数从 8 线性减少到 0,即平均为 4,总共 4.9=36 .

更一般地说,平均值为 (N-1)/2,总数为 N.(N-1)/2

因此,I(N) ~ N²/2,就迭代次数而言。

就内存访问 (R+W) 而言,它是双倍数:A(N) ~ N²。 (外循环中的额外访问增加了微不足道的 N 贡献。)