algorithm - 这个程序是二次的还是线性的？

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⁵)。