整数运行时的大 O 和

Question

我一直在尝试学习 Big O，但对我刚遇到的算法感到困惑。算法是：

void pairs(int[] array){
  for (int i=0; i < array.length; i++){
    for (int j=i+1; j<array.length; j++){
      System.out.println(array[i]+","+array[j]);
    }
  }
}

我认为第一个 for 循环是 O(n)，我知道第二个 for 循环是 O(1/2*n(n+1))。问题的答案是函数的运行时间是 O(n^2)。我将 O(1/2*n(n+1)) 简化为 O(1/2*(n^2+n))。所以我很困惑，因为我认为你需要将两个运行时间项相乘，因为 for 循环是嵌套的，这将得到 O(n) * O(1/2*(n^2+n))。我将其简化为 O(1/2n^3 + 1/2n^2)。据我对 Big O 的了解，您只保留最大项，因此这将减少到 O(n^3)。谁能帮我解决我哪里出错了？不确定答案是 O(n^2) 而不是 O(n^3)。

Answer 1

你的错误是将第二个循环计算为 O(1/2n^2)...
首先，您可以清楚地看到它被限制为 N-1（当 j = 0 时）

第一个循环显然是N
第二个循环是 N-1 的 MAX...
因此，O(N^2)...

如果我们多检查一下，当 i=0、
时，第二个循环将运行 N-1 然后 N-2 为 i=1,
i=n-1、

一次

这是1/2n(n-1) = 1/2n^2 - 1/2n = O(n^2)
注意这也包括外循环的所有迭代！

Answer 2

当您说内部循环是 O(1/2*n(n+1)) 时，您实际上是在描述两个循环的大 O 复杂性。

说外层循环的复杂度为O(N)，基本上就是它的循环体运行s N次。但是为了计算内循环的复杂性，您已经考虑了外循环的 all 次迭代，因为您将内循环的次数加起来运行s外循环的所有迭代。如果你再乘以 N，你会说外循环本身是 re-运行再 N 次。

换句话说，您的分析表明内部循环体（System.out.println 调用）总共运行s 1/2*n(n+1) 次。这意味着双循环组合的整体复杂度为 O(1/2*n(n+1)) = O(n^2)。二循环组合的整体复杂度描述了最里面的代码有多少次运行.

整数运行时的大 O 和

Big O sum of integers runtime

algorithm

big-o