data-structures - 以下算法的时间复杂度如何为0(n^2)

Question

所以我是一个学习时间复杂度的初学者，如果有人能解释一下：

For (i := 0; i < n; i = i + 1)
    For (j := i; j < n; j = j + 1)

时间复杂度为O(n 2 ⁾，我知道这是n次工作，但是如何？另外，如果您能告诉我是什么意思，那就太好了。:=

标签： data-structurestime-complexity

Answer 1

让我们稍微修改一下代码：

x = 0
For (i := 0; i < n; i = i + 1)      //it says: let i be 1, 2, ..., until n - 1
    For (j := i; j < n; j = j + 1)  //it says: let j be i, i+1, ..., until n - 1
        x = x + 1

的价值x是多少？

For很容易计算第二个将运行多少次。

它从 0 开始到 n-1，然后从 1 到 n-1，从 2 到 n-1，...，从 n-1 到 n-1。所以这意味着，在操作中：

0  1  2 ... (n-1) = (n-1) - 0 + 1 operations =    n    operations
1  2  ..... (n-1) = (n-1) - 1 + 1 operations = (n - 1) operations
2  ........ (n-1) = (n-1) - 2 + 1 operations = (n - 2) operations
        .
        .
        .
      (n-1)                                  =    1    operation 
                                               ___________________
                                              (1 + 2 + 3 + ... + n) 
                                               = (n + 1) * (n / 2) 
                                               =     (n² + n)/2  operations

我们可以看到这些For累加(n² + n)/2运算，所以x = (n² + n)/2.

在复杂性分析中，我们遵循一些规则。我将描述在这种情况下有用的那些：

1 删除乘法常数：

O((n² + n)/2) = O(0.5 * (n² + n)) = O(n² + n)

其背后的理论是，当n变为无穷大时，这些常数不会对函数的行为产生影响。

2 删除具有较低功率等级的项：

O(n² + n) = O(n²)

其背后的理论是，具有最大功率等级的变量（n²在这种情况下）支配着函数的行为，而不是具有最低等级的变量。

这就是为什么我们可以说这些嵌套循环的复杂度是 O(n²)。