algorithm - 递减嵌套for循环的运行时间

Question

我最近参加了一次编程面试，出现了以下代码。面试官告诉我这是一个 O(n*n) 算法，但我很困惑这是怎么回事，考虑到每次外循环运行时内循环运行的次数更少。

绝对不是 O(n)，但为什么是 O(n*n)？

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

Answer 1

这样看。第一次通过 i 时，您将循环 j 99 次。接下来，98、97、96 等，一直到 1。这等于:

1 + 2 + 3 + 4 + 5 + ... + n

对这些 ( triangular) 数字求和的快速方法是使用 attributed to Gauss 技术:

sum = ((n * n) + n) / 2

现在您可以清楚地看到 O(n*n)。