如何进行算法分析

Question

我有如下算法，需要对其进行大O分析。我对这个话题很陌生，但我理解 O(1)、O(n)、O(n²)..O(log n) 和 O(n log n) .

我将如何分析以下算法？

x <== 1
for i = 1 to n
    for j = i to 1 (decrement)
        x <== x + 1

Answer 1

内循环的每一次执行：for j = i to 1，都会运行i步，i从1到n。

所以总的时间复杂度是

1 + 2 + ... + n = n*(n+1)/2 ~ O(n^2)