从 0 到 max/min 值的嵌套循环的时间复杂度

Question

我很难找到与我的情况相似的东西。

伪代码：

int n = some pre-defined value
int d = some pre-defined value (that is at max the same as n, don't know if that's relevant)

for (i = 0; i < n; i++) {
    for (int j = 0; j < Min(i, d); j++) {
        do something
    }
}

我知道第一个循环运行 n 次，这意味着时间复杂度本身是 O(n)，但我不明白第二个循环的时间复杂度是多少。

提前致谢。

Answer 1

如果 d 的最大值是 n，则假设它实际上是 n，因为大 O 表示法是最坏情况的上限。那么你有

for (i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
        do something
    }
}

由于对于 i 的每个值，内部循环从 1 到 i，因此总迭代次数为 1（当 i==1 时），+ 2（当 i==2 时），+ 3（当 i = = 3), 依此类推。一般来说，整个算法运行内部循环体 1 + 2 + 3 + ... + n 次，或者使用封闭形式简化为 n*(n+1)/2 次。这实际上是 N 平方，因为 1/2 的系数可以“忽略”，因为它并没有真正改变图形的形状。

你也可以认为它的长度是“n 的一半”，因为如果你配对相应的最短和最长游程（1 和 n，2 和（n-1），3 和（n-2） , 以此类推，它们的平均值约为 n/2，用大 O 表示法就是 n。这样看，外循环是 n，内循环是 n，所以整个算法是 O(n ^2).

从 0 到 max/min 值的嵌套循环的时间复杂度

Time complexity of a nested loop which goes from 0 to a max/min value

time-complexity