algorithm - 大欧米茄分析

Question

我一直在努力理解它的最佳运行时间:

for t = 1 to n
    sum = 0

    for i = 1 to t
        sum = sum + x[i]

我知道第一个循环会进行 n 次。这是我挣扎的内部循环。 内部循环将第一次进入 n(n+1)/2 ，但下一次进入 n(n+1)/2 -1 。 我不确定如何将其转化为最佳运行时间。

如果可能的话，我可以向正确的方向插入。 谢谢!

Answer 1

为了形象化这一点，我采用了一种方法，在更复杂的情况下想象一个充满正方形的区域或一个充满骰子的体积。每个方 block 代表一个原子步骤。外循环迭代的所有步骤都放在同一行。对于您的情况，它看起来像这样:

t=1 #
t=2 ##
t=3 ###
t=4 ####
t=5 #####

如您所见，它们形成了一个三角形，其高度为 N，宽度也为 N。如果您现在计算正方形 (N * (N + 1)/2)，则内部迭代次数为环形。将其相乘并删除不相关的项，得到复杂度 Θ(N*N)。