java - 对大 O 表示法感到困惑

Question

我有两个问题:

public static void method1(int[] a, int[] b) {
   int sum1 = 0, sum2 = 0;

   for(int i = 0; i < a.length; i++) {
      sum1 += a[i];
   }

   for(int i = 0; i < b.length; i++) { 
      sum2 += b[i];
   }
}

问题 1:这是在 O(n) 中吗？ method1 中有多少循环(不是嵌套循环)重要吗？

问题2:如果有一个怎么办

Arrays.sort(a);

在method1里面，它是什么函数？

Answer 1

Question 1: Is this in O(n)?

没错(这里，n 分别表示两个数组的长度)。

Does it matter how many loops (not nested loops) are in method1?

不是的，只要循环次数固定，每次循环的迭代次数在n中是线性的。更正式地说，如果 C 是某个常数，则 C*n 是 O(n)。

Question 2: What if there is a Arrays.sort(a);

排序通常是O(n logn)，这就是Arrays.sort(int[]) 平均。 documentation对最坏情况下的表现含糊不清:

This algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations.

在最坏的情况下，这显然不能保证 O(n logn)。从字里行间看出它可能是 O(n^2)。

有趣的是，在 JDK7 中，Arrays.sort(Object[])使用与 Arrays.sort(int[]) 使用的算法不同的算法.前者是 TimSort 的改编，因此应该保证 O(n logn) 最坏情况下的性能。不幸的是，文档再次没有详细说明这一点。