对Big 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

问题1:这是否在O(n)中？

这是正确的(这里,n表示两个数组中每个数组的长度).

方法1中有多少循环(不是嵌套循环)是否重要？

只要循环次数是固定的,并且每个循环中的迭代次数是线性的,它就不会n.更正式的是,如果C有些不变,那C*n就是O(n).

问题2:如果有的话怎么办？ Arrays.sort(a);

排序通常O(n logn),这就是Arrays.sort(int[])不平均.该文档是含糊不清的最坏情况下的性能:

该算法在许多数据集上提供O(n log(n))性能,导致其他快速降序降级为二次性能,并且通常比传统(单枢轴)Quicksort实现更快.

O(n logn)在最坏的情况下,这显然不能保证.在线之间阅读表明它可能是O(n^2).

值得注意的是,在JDK7中,Arrays.sort(Object[])使用的算法与使用的算法不同Arrays.sort(int[]).前者是TimSort的改编版,因此应该保证O(n logn)最坏情况下的表现.不幸的是,文档再次没有拼写出来.