嵌套 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
贡献。)
如何找到以下算法的 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
:
| 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
贡献。)