這個程序是二次的還是線性的？

Question

我有以下僞代碼：

for i=1 to 3*n 
     for j=1 to i*i 
       for k=1 to j 
        if j mod i=1 then 
         s=s+1 
        endif 
       next k 
     next j 
next i 

當我要分析的部分S = S + 1中執行的次數，假設該操作需要一定的時間，我結束了一個二次複雜性或它是線性的嗎？ n的值可以是任何正整數。

，我所做的計算如下：

Answer 1

非也二次，但至少應該是多項式。

它經歷了3n次迭代。

在每次迭代中，它都做了更多的9n 。

在每一個它可以達到9n 更多。

所以我認爲這將是O（n ）。

Answer 2

當談論運行時間時，您應該始終明確您正在定義的運行時間。

如果我們假設您以n的方式談論您的運行時間，則答案爲O(n^5)。這是因爲你在做什麼歸結到這一點，當我們擺脫了持續性因素的：

do n times: 
    do n^2 times: 
     do n^2 times: 
      do something 

而且n * n^2 * n^2 = n^5