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，您循环了j99 次。接下来，98、97、96 等，一直到 1。这等于：

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

对这些（三角形）数求和的一种快速方法是使用Gauss的技术：

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

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

Answer 2

for i = 0：内循环运行 99 次
for i = 1：内循环运行 98 次
for i = 2：内循环运行 97 次
for i = 3：内循环运行 96 次
。
.
.
for i = 99：内循环运行 0 次

如果我们计算 EOP 的数量，比如说 #(EOPs) := S，那么 S = 0 + 1 + 2 + 3 + .... + 99 所以 S = (99* (99 + 1)) / 2 <= > S = (99*99 + 99) / 2 => S <= 1/2 * 99^2 + 99 <=> S <= 99^2 + 99 <=> S <= 99^2 + 99^2 <=> S <= 2* 99^2 所以让 n = 99 和 c = 2，我们得到 S <= c*n^2 那么 S 的阶数是 n^2。您提交的程序片段具有 n^2 的顺序

Answer 3

该算法的运行时间复杂度或最差转换复杂度为 O(n*n)。这背后的简单推理来自数学，

当 i = 0 时，j 将从 j=1 运行到 j = n（进行 n 次比较）当 i = 1 时，j 将从 j=2 运行到 j = n（进行 n-1 次比较） .... 当 i = n-1，j 将从 j=n 运行到 j=n（进行 1 次比较）

如果你加上这个，(1) + (2) + (3) + ... + (n-1) + (n)，你基本上计算了前 n 个自然数的总和，即 n*(n+1 )/2。扩展这个你得到 (n n + n)/2。这本质上具有 n n 的时间复杂度，或者 O(n*n) 的大 oh 符号。