具有独立嵌套循环的大 O

Question

仍在努力掌握 Big O 的复杂性。

我有这个循环：

t:=0
for (i:=1;i<n+1;i++)
    for (j:=1;j<n+1;j++)
        t:=t+i+j;

(Also shown in this image)

如果嵌套循环依赖于外部循环，我相信它会是 O(n^2)。我认为每个循环都是 O(n)。因为它们不相互依赖，这是否意味着这个算法是 O(n)，或者它仍然是 O(n^2) 因为每个循环？

外层循环从 1 到 n+1... 所以 O(n)... 嵌套循环也是... 所以 O(n*n)?

Answer 1

外循环进行 N 次迭代。对于每个外循环迭代，内循环进行 N 次迭代。所以总迭代次数为N^2.

复杂度是O(N^2)，不是O(N)。

Answer 2

内循环运行n次。外循环也跑了n次。所以我们有 n 个外循环乘以 n 个内循环，两个循环加起来为 O(n*n)。

Answer 3

这个的时间复杂度可以是 O(n^2)、O(n^3)、O(n^4) 等中的任何一个。但是因为我们选择 "CEIL" 以上所有值中的最小值，所以复杂度仍然为 O(n^2)。

Big O with independent nested loops