嵌套循环内代码的时间复杂度
Time complexity of code within nested loop
给出
for (int i = 1; i <= n - 1; i++)
for (int j = i + 1; j <= n; j++)
Console.WriteLine(i, j);
我知道外循环运行 4n - 1 次，内循环运行 3n^2 - 3 次，但是我不明白为什么打印语句运行 n(n - 1)/2 次。我只得到 n(n - 1) 作为我的时间复杂度，但幻灯片说 n(n - 1)/2。我错过了什么？
- 对于 i = 1，j 从 2 到 n 变化 => n-1 次
- 对于 i = 2，j 从 3 变化到 n => n-2 次
...
...
- 对于 i=n-1 j 从 n 到 n => 1 次变化
所以操作次数=> (n-1) + (n-2) + (n-3) + .... +1
求解 n(n-1)/2（记住 n 个自然数求和的公式 - https://cseweb.ucsd.edu/groups/tatami/handdemos/sum/
您并没有遗漏太多，因为 n(n - 1) 和 n(n - 1)/2 的大 O 界是 O(n^2)。你展示的双循环将以 O(n^2) 为上限，我认为这是这里的要点。
给出
for (int i = 1; i <= n - 1; i++)
for (int j = i + 1; j <= n; j++)
Console.WriteLine(i, j);
我知道外循环运行 4n - 1 次，内循环运行 3n^2 - 3 次，但是我不明白为什么打印语句运行 n(n - 1)/2 次。我只得到 n(n - 1) 作为我的时间复杂度，但幻灯片说 n(n - 1)/2。我错过了什么？
- 对于 i = 1，j 从 2 到 n 变化 => n-1 次
- 对于 i = 2，j 从 3 变化到 n => n-2 次
...
...
- 对于 i=n-1 j 从 n 到 n => 1 次变化
所以操作次数=> (n-1) + (n-2) + (n-3) + .... +1 求解 n(n-1)/2（记住 n 个自然数求和的公式 - https://cseweb.ucsd.edu/groups/tatami/handdemos/sum/
您并没有遗漏太多，因为 n(n - 1) 和 n(n - 1)/2 的大 O 界是 O(n^2)。你展示的双循环将以 O(n^2) 为上限，我认为这是这里的要点。