包含嵌套循环的代码的时间复杂度

Question

i := n;
WHILE i > 1
    FOR j := i to n DO
        X;
    END
    FOR j := 3*i to 3*n DO
        X;
    END
    DEC(i); (* i decrement *)
END

对于此伪代码，我必须根据 n 计算函数 f: N -> N。我是第一次做这样的事情，所以我什至不知道我的方法是否正确。所以，在第一行我有一个常数时间。 while循环运行n-1次+n次比较和n-1个常数时间递减。第一个 for 循环运行 n-i+1 次。第二个 for 循环运行 3n-3i+1 次。所以（我认为）这将是公式：f(n)=1+((n-1)+n+(n-1))*((n-i+1)+(3n-3i+1))那就是 f(n)=12n^2 -12ni -2n +8i -3

但现在我有 n 和 i 变量？我如何摆脱 i?

Answer 1

假设"to n"表示"the last value is n-1"（时间复杂度不重要-看最后解释）

让我们把 f(X) = 时间复杂度设为运行 X.

总时间为：

1 +
0 + 0 +                   // i=n
f(X) + 3*f(X) +           // i=n-1
2*f(X) + 6*f(X) +         // i=n-2
3*f(X) + 9*f(X) +         // i=n-3
...
(n-2)*f(X) + 3*(n-2)*f(X) // i=2
------------------------------
1 + 4*f(X) + 8*f(X) + 12*f(X) + ... + 4*(n-2)*f(X)

这个总和等于：

1 + 4*f(X)*(1+2+3+...+n-2) = 1 + 4*f(X)*(n-2)*(n-1)/2

但是常数不影响该函数的趋势 => 结果是：

O(2*f(X)*(n-2)(n-1)) = O(f(X)*(n^2))

如果 X 只是一个简单的操作 (O(1))，则为 O(n^2)。

P.S.:

如果您不确定常数是否影响最终结果，请尝试计算：

          1 + 4*f(X)*(n-2)*(n-1)/2 
   lim  ---------------------------
n->infinite      f(X)*n^2

你会得到一个有限数（也就是说分子和分母是相似的）。

包含嵌套循环的代码的时间复杂度

Time-complexity of code containing nested loops

algorithm

pseudocode

time-complexity