給定代碼的時間複雜度？

Question

是什麼時間該代碼的複雜性：

for (i=1 to n) 
    for (j=1 to i^2) 
     if ((j mod i)==0) 
       for (k=1 to j) 
        write ("*"); 

我發現我，j和k之間的這種關係： 例如，n = 4，從而：

i  j    k 
1  1-1   1 k run for 1time 
2  1-4   1,2,3,4 k run for 2 and 4 times 
3  1-9   1,2,3,4,5,6,7,8,9 k run for 3, 6 and 9 times 
4  1-16   1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 k run for 4, 8, 12 and 16 times 

但我不能找到它的複雜性

Answer 1

與較大的n值相比，j mod i = 0的出現可以忽略不計。對於前兩個嵌套循環來說，顯然複雜度是從1到n的pow（i，2）的總和。所以我們可以把複雜度看作O（n^3）。