问这个for循环的复杂度是多少? for (int j= i；j< n；j++)？

EN

如果您尝试将其可视化为一个矩阵，其中线代表i，每列代表j，您将看到这与边n形成了一个三角形

n为4的示例

0 1 2 3
  1 2 3
    2 3
      3

内部循环的复杂度(平均)为n/2，为O(n)。总复杂度为n*(n+1)/2或O(n^2)

这需要的步骤数是一个Triangle Number。下面是我用LINQpad编写的一小段代码(是的，很抱歉用C#回答，但希望这仍然是可读的)：

void Main()
{
    long k = 0;

    // Whatever you want
    const int n = 13;

    for (int i = 0; i < n; i++)
    {
        for (int j = i; j < n; j++)
        {
            k++;
        }
    }

    k.Dump();

    triangleNumber(n).Dump();

    (((n * n) + n) / 2).Dump();
}

int triangleNumber(int number)
{
    if (number == 0) return 0;
    else return number + triangleNumber(number - 1);
}

所有3个打印语句(LINQpad中的.Dump())都会产生相同的结果(91表示我选择的n的值，但您也可以选择您想要的值)。

正如其他人所指出的，这就是O(n^2)。(有关这方面的更多详细信息，您也可以查看this Q&A )。

我们可以看到循环的总迭代次数是n*(n+1)/2，我假设您已经从上面的解释中清楚地了解了这一点。

现在让我们以一种简单的逻辑方式找到渐近的时间复杂度。大哦，当n的值是一个大数字时，就开始玩了，在这种情况下，我们不需要考虑除以2(2是一个常数)，因为(大数字/ 2)也是一个大数字。

这就只剩下n*(n+1)了。

如上所述，由于n是大数，(n+1)可以近似为(n)。从而给我们留下了(n*n)。

因此时间复杂度为O(n^2)。