computation-theory - 计算以下代码的代码复杂度

Question

我觉得在最坏的情况下，当 j=i 或 j=i^2 然后循环运行额外的 i + i^2 次时，条件只有两次为真。在最坏的情况下，如果我们取内部 2 个循环的总和，它将是 theta(i^2) + i + i^2 ，它等于 theta(i^2) 本身；外循环上 theta(i^2) 的总和给出 theta(n^3)。那么，答案是 theta(n^3) 吗？

标签： computation-theory

Answer 1

对于固定的i，i整数是。因此，内部循环使用参数执行次数为和守卫执行次数。因此，复杂度函数由下式给出：1 ≤ j ≤ i2j % i = 0{i,2i,...,i2}ii * m1 ≤ m ≤ ii2T(n) ∈ Θ(n4)

T(n) = ∑[i=1,n] (∑[j=1,i2] 1 + ∑[m=1,i] ∑[k=1,i*m] 1)
     = ∑[i=1,n] ∑[j=1,i2] 1 + ∑[i=1,n] ∑[m=1,i] ∑[k=1,i*m] 1
     = n3/3 + n2/2 + n/6 + ∑[i=1,n] ∑[m=1,i] ∑[k=1,i*m] 1
     = n3/3 + n2/2 + n/6 + n4/8 + 5n3/12 + 3n2/8 + n/12
     = n4/8 + 3n3/4 + 7n2/8 + n/4