如何确定以下算法的复杂度？

Question

S <--- 0

for i==1 to n do

for j==1 to i do

   S <--- S+1  

end for

end for

write(S)

我不知道如何解决这个问题。

我尝试计算 j 循环的复杂度，但无法得到解决方案

Answer 1

第一个循环有 n 个步骤，因此具有线性复杂度。嵌套循环的平均公式将帮助您进一步理解这一点。

首先，有n步。那么它有n-1步。那么它有n-2步。并且它会逐渐减少，直到达到一步。所以平均值是：

(1 + 2 + 3 + ... + n) / n

这是一个算术级数。您会看到，将第一个元素与最后一个元素配对是 n + 1，将第二个元素与倒数第二个元素配对是 2 + n - 1 = 1 + n，...将左侧的第 i 个元素与来自的第 i 个元素配对右边，你有 i + n - i + 1 = n + 1。所以，你有 n / 2 对 n + 1，因此等于 n * (n + 1) / 2 并且如果我们将它除以 n为了得到平均值，我们得到 n * (n + 1) / 2n = (n + 1) / 2，大约是 n 的一半，也就是说，如果 n -> 无穷大，则将除法渲染为2 不相关，因此复杂度是二次的，即 O(n^2)。在这个算法之后，你写出结果，这可能与复杂性无关。