8

我有两个问题：

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，它是什么功能？

4

2 回答 2

7

问题 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)) 性能，导致其他快速排序降低到二次性能，并且通常比传统的（单轴）快速排序实现更快。

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

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

于 2013-03-16T22:05:39.663 回答
1

  1. 一种。它是 O(n)，其中 n = 输入长度（总）
    b。是的，有多少循环很重要：如果它是恒定数量的循环 k，那么它就是 O(k*n)，通常被认为是 O(n)，但是如果 k >= n，则应该考虑到这一点

  2. Arrays.sort(a);使用合并排序实现，该排序在平均和最坏情况下都在 O(n log n) 中运行（不像 NPE 所说的那样！）。

MrSmith42 的更新：

来自http://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html：
sort(Object[]) 使用的算法不必是 MergeSort，但它确实必须保持稳定。）

并且：

实施说明：排序算法是 Vladimir Yaroslavskiy、Jon Bentley 和 Joshua Bloch 的 Dual-Pivot Quicksort。该算法在许多数据集上提供 O(n log(n)) 性能，导致其他快速排序降低到二次性能，并且通常比传统的（单轴）快速排序实现更快。

于 2013-03-16T22:10:28.163 回答