计算代码的运行时间

Question

如何计算给定伪代码的时间复杂度？？我想知道它是如何计算的。

sum ← n + 351
for (int i = 1; i < n + 2; i++) do
    sum ← sum + i + 355 + A[i]
    for (int j = 0; j ≤ i; j++) do
        sum ← sum * A[j] + j
    end-for (j)
    sum ← sum + 352 * n
    for (int k = 0; k < n - 1; k++) do
        sum ← sum * k + A[k]
    end-for (k)
    sum ← sum + 2 * n + 354
end-for (i)
sum ← sum + 2 * n + 356

Answer 1

你可以看看每个循环的复杂度。

外层循环是顺序n

内部循环也上升到 n（实际上 i 上升到 n）

合并起来就是O(n^2)

计算代码的运行时间

Calculating the runtime of the code

algorithm

time-complexity