大O帶獨立嵌套環

Question

還在努力把握大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^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）。