1

「Big-O」が何であるか、実際にどのように使用するかを本当に理解できないので、誰かが簡単な説明とJavaでのプログラミングの例を教えてくれることを願っています.

次の質問があります。

  • BigO(1)、BigO(n)、BigO(n2)、BigO(log(n)) という用語の意味 (できるだけ簡単に) と Java での使用方法を教えてください。

  • 既存の Java コードから Big-O をどのように計算しますか?

  • Big-O ソートをどのように使用しますか
  • Big-O 再帰をどのように使用しますか

誰かが助けてくれることを願っています。

よろしくお願いします

4

3 に答える 3

5

Big O は、入力サイズの増加に応じてアルゴリズムがスケーリングする速さを示すために使用されます。

O(1) は、入力サイズが増加しても実行時間は変わらないことを意味します

O(n) は、入力サイズが 2 倍になると、実行時間が多かれ少なかれ 2 倍になることを意味します

O(n^2) は、入力サイズが 2 倍になると、実行時間が多かれ少なかれ 4 倍になることを意味します

O(f(n)) は、入力サイズが 2 倍になると、実行時間が約 f(2n) に増加することを意味します。

Big-O、ソート、再帰について。

Big-O ソートは実際にはアルゴリズムではありません。ただし、Big O を使用して、並べ替えアルゴリズムの速度を確認できます。

再帰関数の Big-O を計算するには、Master Theoremを使用することをお勧めします。

Big O を決定するためのガイドライン:

通常、入力サイズを決定する必要があります (配列の長さ、リンクされたリスト内のノードの数など)。

次に、入力サイズが 2 倍になるとどうなるかを自問してください。それともトリプル？各要素を通過する for ループがある場合: 

//say array a has n elements
for (int i = 0; i < n; i++) {
    // do stuff 
    a[i] = 3;
}

次に、n を 2 倍にすると、ループの実行時間が 2 倍になるため、O(n) になります。n を 3 倍にすると、所要時間が 3 倍になるため、コードは入力サイズに比例してスケーリングします。

2D 配列があり、for ループがネストされている場合:

// we say that each dimension of the array is upper bounded by n,
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        // do stuff
        a[i][j] = 7;
    }
}

n が 2 倍になると、コードには 2^2 = 4 倍の時間がかかります。入力サイズが 3 倍になると、コードには 3^2 = 9 倍の時間がかかります。したがって、Big O は O(n^2) です。

于 2013-06-14T22:32:43.777 に答える
2

Big-O 表記法は、入力が非常に大きい場合にコンピューター アルゴリズムのパフォーマンスを示すために作成された表記法です。

Java での 3 つの簡単なプログラミング例:

O(1):

for (int i=0; i<3; i++) {
   System.out.println(i);
}

O( n ):

int n = 1000000; /* Some arbitrary large number */    
for (int i=0; i<n; i++) {
   System.out.println(i);
}

O( n 2 ):

int n = 1000000; /* Some arbitrary large number */    
for (int i=0; i<n; i++) {
   for (int j=0; j<n; j++) {
      System.out.println(i * j);
   }
}

詳細: http://en.wikipedia.org/wiki/Big_O_notation

于 2013-06-14T22:38:36.030 に答える
1

ビッグ O (小さい O とは対照的に大きい O の文字) は、入力サイズ (n) が変化したときにアルゴリズムがどのようにスケーリングするかを示します。数字は

たとえば、n が 100 から 200 アイテムの 2 倍になる場合、

  • O(1) アルゴリズムはほぼ同じ時間がかかります。
  • O(n) アルゴリズムは 2 倍の時間がかかります。
  • O(n^2) アルゴリズムは 4 倍の時間がかかります (2^2)
  • O(n^3) アルゴリズムでは、8 倍の時間がかかります (2^3)

等々。

log(n) は「n の桁数」として理解できることに注意してください。これは、2 桁 (99 など) の n から 2 倍の桁数 (9999 などの 4 桁) の n に変更した場合、実行時間は 2 倍になるだけであることを意味します。これは通常、データを 2 つの山に分割し、それぞれを個別に解決して、並べ替えなどで解決策をマージした場合に発生します。

通常、入力データの各ループは n で乗算されます。したがって、単一のループは O(n) ですが、すべての要素を他のすべての要素と比較する必要がある場合は、O(n^2) になります。時間は相対的であるため、n の値が小さい場合、低速の O(n) アルゴリズムは高速の O(n^2) アルゴリズムよりも優れている可能性があることに注意してください。

また、O は最悪のケースであることに注意してください。したがって、一般的に高速に実行されるクイックソートは O(^2) です。これは、すべての要素を他のすべての要素と比較する哀れな入力データがあるためです。

ほとんどのアルゴリズムは小さなデータセットに対して高速であるため、これは興味深いことですが、O(n^2) または O(n^3 ）またはさらに悪い。数値は相対的であるため、特定のアルゴリズムが遅いか速いか、入力サイズを 2 倍にしたときに最悪の場合がどのように見えるかについては何も言いません。

于 2013-06-14T23:03:51.260 に答える