4

最悪の場合の時間の複雑さを与える方法を見つけようとしています。私の分析についてはよくわかりません。ネストされたforループの大きな Oを読みましたn^2。内部にforループがあるループの場合、これは正しいですか?while

// A is an array of real numbers.
// The size of A is n. i,j are of type int, key is
// of type real. 
Procedure IS(A)    
for j = 2 to length[A]     
{                
   key = A[ j ]               
   i = j-1   
   while i>0 and A[i]>key    
   {       
      A[i+1] = A[i]                         
      i=i-1                    
   }                
   A[i+1] = key      
}

これまでのところ、私は持っています: 

j=2 (+1 op)  

i>0 (+n ops)   
A[i] > key (+n ops)

so T(n) = 2n+1?

しかし、最悪の場合の時間の複雑さを分析するため にwhileandループの中に入る必要があるかどうかはわかりません...for

ここで、それがしっかりと束縛されていることを証明する必要があります。それがビッグ シータです。

ネストされたforループには Big O of があることを読みましたn^2。これはビッグシータにも当てはまりますか? そうでない場合、ビッグシータを見つけるにはどうすればよいでしょうか?!

**C1= C sub 1、C2= C sub 2、および no= n naught すべて正の実数の要素です

を見つけるためT(n)に、値をj調べ、while ループが実行された回数を調べました。

values of J:   2, 3, 4, ... n  
Loop executes: 1, 2, 3, ... n

分析:
while ループの実行の合計を取得し、(n(n+1))/2 これを my として割り当て、T(n)によって厳密に制限されていることを証明しn^2ます。あれはn(n+1)/2= θ(n^2)

スクラッチワーク:

Find C1, C2, no є R+ such that 0 ≤ C1(n^2) ≤ (n(n+1))/2 ≤ C2(n^2)for all n ≥ no

To make 0 ≤ C1(n) true, C1, no, can be any positive reals   
To make C1(n^2) ≤ (n(n+1))/2, C1 must be ≤ 1  
To make (n(n+1))/2 ≤ C2(n^2), C2 must be ≥ 1

PF:

Find C1, C2, no є R+ such that 0 ≤ C1(n^2) ≤ (n(n+1))/2 ≤ C2(n^2) for all n ≥ no
Let C1= 1/2, C2= 1 and no = 1.

  1. 0 ≤ C1(n^2) が真であることを示す C1(n^2)= n^2/2
    n^2/2≥ no^2/2
    ⇒no^2/2≥ 0
    1/2 > 0
    よって C1 (n^2) ≥ 0 は真であることが証明されています!

  2. C1(n^2) ≤ (n(n+1))/2 が真であることを示す C1(n^2) ≤ (n(n+1))/2
    n^2/2 ≤ (n(n+1) ))/2 n^2 ≤ n(n+1)
    n^2 ≤ n^2+n
    0 ≤ n

    n ≥ no = 1 であるため、これは正しいことがわかっています。
    したがって、C1(n^2) ≤ (n(n+1))/2 は正しいことが証明されています。

  3. (n(n+1))/2 ≤ C2(n^2) が真であることを示します (n(n+1))/2 ≤ C2(n^2)
    (n+1)/2 ≤ C2(n)
    n+1 ≤ 2 C2(n)
    n+1 ≤ 2(n)
    1 ≤ 2n-n
    1 ≤ n(2-1) = n
    1≤ n
    また、n ≥ no = 1 なので、これが真であることがわかっています。

    したがって、1、2、および 3 により、
    0 ≤ C1(n^2) ≤ (n(n+1))/2 ≤ C2( n^2) すべての n ≥ no

皆さんのことを教えてください... 私はこの資料を理解しようとしており、皆さんの意見を求めています!

4

3 に答える 3

5

ウィキペディアが O(N 2 ) と主張する挿入ソート アルゴリズムを実装しているようです。

通常、Big-O を扱うときは、定数 C ではなく、変数 N に基づいてコンポーネントを分類します。あなたの場合、あなたがする必要があるのはループを見ることだけです。

あなたの2つのループは（悪い場合）です：

for j=2 to length[A]
    i=j-1
    while i > 0
        /*action*/
        i=i-1

要素の数に直接関係するため、外側のループは O(N) です。

内側のループが外側のループの進行状況にどのように依存するかに注目してください。つまり、(off-by-one の問題は無視して) 内部ループと外部ループは次のように関連しています。

jのインナー
値ループ
----- -----
  2 1
  3 2
  4 3
  N N-1
----- -----
合計 (N-1)*N/2

したがって、遭遇する合計回数/*action*/は (N 2 - N)/2、つまり O(N 2 ) です。

于 2009-03-18T02:33:17.247 に答える
2

ネストされたループの数を調べることは、解決策を得るための最善の方法ではありません。重い負荷Nの下で、コードで実行されている「作業」を確認することをお勧めします。たとえば、

for(int i = 0; i < a.size(); i++)
{
  for(int j = 0; j < a.size(); j++)
  {
    // Do stuff
    i++;
  }
}

O（N）です。

関数fは、gのBig-OhとgのBig-Omegaの両方にある場合、gのBig-Thetaにあります。最悪のケースは、データAが単調減少関数である場合に発生します。次に、外側のループが繰り返されるたびに、whileループが実行されます。各ステートメントが1の時間値を提供した場合、合計時間は5 *（1 + 2 + ... + n-2）= 5 *（n-2）*（n-1）/2になります。データへの二次依存。ただし、データAが単調に増加するシーケンスである場合、条件A[i]>キーは常に失敗します。したがって、外側のループは一定時間N-3回実行されます。fの最良のケースは、データに線形依存します。平均的なケースでは、Aの次の番号を取得し、以前に発生した並べ替えでその場所を見つけます。平均すると、この数はこの範囲の中央になります。

于 2009-03-18T04:14:13.230 に答える
0

タスクを完了するためにループ内の要素が何回見られるかについてのビッグオー（基本的に）。

たとえば、O(n) アルゴリズムは、すべての要素を 1 回だけ繰り返し処理します。AO(1) アルゴリズムは、すべての要素を反復する必要はまったくありません。インデックスがあるため、配列内のどこを探すべきかを正確に認識します。この例は、配列またはハッシュ テーブルです。

ループ内のループが O(n^2) である理由は、ループ内のすべての要素を ^2 回反復する必要があるためです。ループのタイプを変更することは、基本的に反復回数に関するものであるため、それとは関係ありません。

必要な反復回数を減らすことができるアルゴリズムへのアプローチがあります。これらの例は、 Quicksort のような「分割統治」アルゴリズムであり、正しく思い出せば O(nlog(n)) です。

あなたが達成しようとしていることをより具体的に知らずに、あなたの例のより良い代替案を考え出すことは困難です.

于 2009-03-18T02:34:22.033 に答える