時間の複雑さ（Java、Quicksort）

Question

私は、時間の複雑さを計算すること（Big O表記法）に関する非常に一般的な質問があります。 QuickSortの最悪の時間の複雑さがO（n^2）であると言うとき（いつでもピリオドになる配列の最初の要素を選び、配列は逆にソートされます）、O（n^2）？ if/else文で比較される人は何人ですか？あるいは、スワップの総数を数えるだけですか？一般的にどのような "ステップ"がビッグO表記を計算するかを知っていますか？

クイックの

Answer 1

最悪のケースをソートクイックソートの 最悪の場合はされ
私は、これは非常に基本的な質問です知っているが、私はGoogleで、ほぼすべての記事を読みましたが、まだそれを考え出したていません配列が逆ソートされた場合、通常ソートされ、すべての要素は等しい。

---

ビッグああ
は、私たちが最初に何かのビッグああ、意味を理解しましょう、と言った理解します。

上限と漸近の上限がある場合は、O表記を使用します。 O（g（n））= {f（n）：正のcとnが存在する。 _o、
のように、関数g（n） ように、すべてのnに対して0 <は= F（N）< = CG（N）> = N

} O

---

はどのように我々はビッグああ計算していますか？
Big-Ohは基本的に入力サイズによってプログラムの複雑さが増すことを意味します。

import java.util.*; 
class QuickSort 
{ 
    static int partition(int A[],int p,int r) 
    { 
     int x = A[r]; 
     int i=p-1; 
     for(int j=p;j<=r-1;j++) 
     { 
      if(A[j]<=x) 
      { 
       i++; 
       int t = A[i]; 
       A[i] = A[j]; 
       A[j] = t; 
      } 
     } 

     int temp = A[i+1]; 
     A[i+1] = A[r]; 
     A[r] = temp; 
     return i+1; 
    } 
    static void quickSort(int A[],int p,int r) 
    { 
     if(p<r) 
     { 
      int q = partition(A,p,r); 
      quickSort(A,p,q-1); 
      quickSort(A,q+1,r); 
     } 
    } 
    public static void main(String[] args) { 
     int A[] = {5,9,2,7,6,3,8,4,1,0}; 
     quickSort(A,0,9); 
     Arrays.stream(A).forEach(System.out::println); 
    } 
} 

は、次のステートメントを考慮する：ここ

コードである

ブロック1：

int x = A[r]; 
int i=p-1; 

ブロック2：

if(A[j]<=x) 
{ 
    i++; 
    int t = A[i]; 
    A[i] = A[j]; 
    A[j] = t; 
} 

ブロック3：

int temp = A[i+1]; 
A[i+1] = A[r]; 
A[r] = temp; 
return i+1; 

ブロック4：各ステートメントを仮定

if(p<r) 
{ 
    int q = partition(A,p,r); 
    quickSort(A,p,q-1); 
    quickSort(A,q+1,r); 
} 

は、一定時間Cを取ります。それぞれのブロックが何回計算されたかを計算しましょう。

最初のブロックは2c回実行されます。 2番目のブロックが実行されました5c回。 thirstブロックが実行されました4c回。

入力の大きさが変わっても同じ回数だけ文が実行される回数を意味するO（1）と書いています。すべて2c、5cおよび4cはすべてO（1）です。

しかし、我々は、第二のブロック上

for(int j=p;j<=r-1;j++) 
{ 
    if(A[j]<=x) 
    { 
     i++; 
     int t = A[i]; 
     A[i] = A[j]; 
     A[j] = t; 
    } 
} 

のループを追加する場合には、n回（RPがnに等しい入力の大きさを想定）、すなわち、NO（1）倍すなわちに対して実行に）。しかし、これは毎回n回実行されません。したがって、平均の場合O（log n）、すなわち少なくともlog（n）個の要素が横断される。

パーティションがO（n）またはO（log n）を実行することを確認しました。最後のブロック（quickSortメソッド）は、O（n）で実行されます。我々はそれをn回を実行する包囲ループと考えることができる。したがって、全体の複雑さは、O（n ）またはO（nlog n）のいずれかです。

Answer 2

これは、主にサイズが大きくなる（n）ためにカウントされます。したがって、クイックソートでは配列のサイズです。アレイの各要素に何回アクセスする必要がありますか？ 1回だけ各要素にアクセスする必要がある場合は、O（n）などとなります。

nが大きくなるにつれて増加する温度変数/ローカル変数がカウントされます。 nが大きくなっても大きく成長しないその他の変数は定数として数えることができます：O（n）+ c = O（n）

Answer 3

他の人の言葉に加えて、しかし、私が大学のアルゴリズムクラスから正しくリコールした場合、スワップオーバーヘッドは通常、比較時間に比べて最小であり、場合によっては（問題のリストが既にソートされている場合）0になります。

たとえば、線形検索式は

T = K * N/2である

Tは合計時間である

。 Kは総計算時間を定義する一定の定数である。 Nはリスト内の要素の数です。

平均では、比較回数はN/2回です。

しかし、我々は、以下にこれを書き換えることができる：

これはなり

T =（K/2）* N

またはKを再定義、

T = K * N.時間がNの大きさに正比例することは明らかです。これは私たちが本当に気にしていることです。 Nが大きく増加すると、それが本当に重要な唯一のものになります。

一方、バイナリ検索では、対数的に大きくなります（O log（N））。