8

2 つの質問があります。

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は 2 つの配列のそれぞれの長さを示します)。

method1 に含まれるループ (ネストされたループではない) の数は重要ですか?

ループ数が固定されていて、各ループの反復回数が線形である限り、そうではありませんn。より正式には、Cが何らかの定数である場合、 C*nisO(n)です。

質問 2:Arrays.sort(a);

並べ替えは通常O(n logn)、これがArrays.sort(int[])平均して行われることです。ドキュメントは、最悪の場合のパフォーマンスについて曖昧です。

このアルゴリズムは、多くのデータ セットに対して O(n log(n)) のパフォーマンスを提供するため、他のクイック ソートのパフォーマンスは 2 次パフォーマンスに低下します。通常、従来の (1 ピボット) クイック ソートの実装よりも高速です。

これは明らかに最悪の場合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(n) と見なされる O(k*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 である必要はありませんが、MergeSort である必要があります。安定します。）

また:

実装に関する注意: ソート アルゴリズムは、Vladimir Yaroslavskiy、Jon Bentley、および Joshua Bloch による Dual-Pivot Quicksort です。このアルゴリズムは、多くのデータ セットに対して O(n log(n)) のパフォーマンスを提供するため、他のクイック ソートのパフォーマンスは 2 次パフォーマンスに低下します。通常、従来の (1 ピボット) クイック ソートの実装よりも高速です。

于 2013-03-16T22:10:28.163 に答える