三重嵌套 for 循环的时间复杂度
Time complexity of a triple nested for loop
我正在努力寻找以下三重嵌套 for 循环的确切时间复杂度和大 Oh 时间复杂度，如果我做得正确，我会感到困惑。
for (int i=1; i<=n; i++)
for (int j=i; j<=n; j++)
for (int k=i; k<j; k++)
sum++;
我知道外层循环运行n次。然后第二个循环 运行s 每次不同的次数，因为它从 i:
开始
n + (n-1) + (n-2) + ... + 2 + 1.
但是，由于我们只关心最坏的情况（即 i=n 时），因此第二个循环将 运行 n-n 次，因为它将从 i=n 开始。当然，这没有意义，但这就是我被卡住的地方。我有 运行 的代码并找到序列的前四个元素：S = 0 + 1 + 4 + 10 + ... +（不确定其余部分）。
抱歉，如果这没有意义，我们将不胜感激！
重要的是要知道像 1+2+3+...+n 这样的所有算术级数都在 O(n^2) 中。因此，您得到三个嵌套循环，每个循环都在 O(n) 中，因此总时间复杂度为 O(n^3)，或者更准确地说，Θ(n^3).
请注意，此处没有“worst-case”或“best-case”，因为步数仅取决于 n，与其他无关。将其与例如排序算法，其中步骤数可能不仅取决于要排序的元素的数量 n，而且还取决于元素的值及其特定顺序。
我正在努力寻找以下三重嵌套 for 循环的确切时间复杂度和大 Oh 时间复杂度，如果我做得正确，我会感到困惑。
for (int i=1; i<=n; i++)
for (int j=i; j<=n; j++)
for (int k=i; k<j; k++)
sum++;
我知道外层循环运行n次。然后第二个循环 运行s 每次不同的次数，因为它从 i:
开始n + (n-1) + (n-2) + ... + 2 + 1.
但是，由于我们只关心最坏的情况（即 i=n 时），因此第二个循环将 运行 n-n 次，因为它将从 i=n 开始。当然，这没有意义，但这就是我被卡住的地方。我有 运行 的代码并找到序列的前四个元素：S = 0 + 1 + 4 + 10 + ... +（不确定其余部分）。
抱歉，如果这没有意义，我们将不胜感激！
重要的是要知道像 1+2+3+...+n 这样的所有算术级数都在 O(n^2) 中。因此，您得到三个嵌套循环，每个循环都在 O(n) 中，因此总时间复杂度为 O(n^3)，或者更准确地说，Θ(n^3).
请注意，此处没有“worst-case”或“best-case”，因为步数仅取决于 n，与其他无关。将其与例如排序算法，其中步骤数可能不仅取决于要排序的元素的数量 n，而且还取决于元素的值及其特定顺序。