時間複雑度の解析

12728 ワード

1.時間の複雑さの定義
一般的に、アルゴリズムで基本的な動作を繰り返し実行する回数は問題規模nの関数であり、T(n)で表し、nが無限大に近い場合、T(n)／f(n)の極限値がゼロに等しくない定数である場合、f(n)はT(n)の同数関数である.T(n)＝O(f(n))と記し、O(f(n)と称する.アルゴリズムの漸進時間複雑度(Oは数量レベルの符号)であり、時間複雑度と略す.
定義:もし問題の規模がnなら、この問題を解くためのあるアルゴリズムに必要な時間はT(n)であり、nの関数である場合、T(n)はこのアルゴリズムの「時間複雑性」と呼ばれる.入力量nが徐々に大きくなると,時間複雑性の限界状況をアルゴリズムの「漸近時間複雑性」と呼ぶ.大きなO表現法を用いて時間の複雑さを表しています.あるアルゴリズムの時間複雑さに注意してください.大Oは上界があるというだけで、f(n)=O(n)を定義すれば、明らかにf(n)=O(n^2)を成立させます.上界をあげますが、最大上界ではありません.しかし、人々は表現する時には前者を表す習慣があります.さらに、一つの問題自体にもその複雑さがあり、もしあるアルゴリズムの複雑さがこの問題の複雑さの下界に達したら、このようなアルゴリズムが最適アルゴリズムと呼ばれます.この説明で使用される基本パラメータはnであり、問題例の規模であり、複雑性または実行時間をnの関数として表現する.ここでの「O」は、階級(order)を表しています.例えば、「二分検索はO(logn)」、つまり「logn級のステップでnの配列を検索します.」記法O(f(n)はnが大きくなると、運転時間はf(n)に比例するスピードで増加することが多いです.この漸進推定はアルゴリズムの理論解析と概ね比較に非常に価値があるが,実践においても詳細に差異が生じる可能性がある.例えば、低付加価値O(n 2)アルゴリズムは、nが小さい場合には、付加価値の高いO(nlogn)アルゴリズムよりも速く動作することができる.もちろん,nが十分大きいと,より遅い上昇関数を持つアルゴリズムはより速く動作するに違いない.
2.時間複雑度計算例
1)正常計算の計算手順

  int num1, num2;
  for(int i=0; i1;
       for(int j=1; j<=n; j*=2) 
       {        
        num2 += num1;
       }
  }

解析:1.ステートメントint num1, num2;の頻度は1である.ステートメントi=0;の頻度は1である.ステートメント

i n； 
 j<=n; j*=2; num2+=num1;の はn＊log 2 nである.T(n) = 2 + 4n + 3n*log2n2. 2.T(n)の 、 いべき 、 べき を する f(n) = n*log2n.nは に かっており、1／nは0に かっており、1／log 2 nは0に かうので、 は3に しい.lim(T(n)/f(n))=(2+4n+3n*log2n)/(n*log2n)= 2*(1/n)*(1/log2n) + 4*(1/log2n) + 32) された ステップ
 してみると、アルゴリズムの さを めるのは が い です.ここはnum 2+=num 1です. には の の です.また、 は が かどうかは されますか?したがって、 のステップは、1. が も い を つける2. の の 3. を きなOで して、 のアルゴリズムを にして を けても い.
1. が い はnum 2+=num 1 2.T(n)=n*log 2 nf(n)=n*log 2 n
3. の 
1) 
アルゴリズムの さは、 の だけではなく、 の および における の にも している. は に しないで、 の の さはすべて の の の さです.これは、アルゴリズムの がいかなるものよりも くないことを する.
2) を める
つまり、 (log)を めます. の は10です. に えば、「 つの は の で された 、10の 」です. えば、5000=5 x 10 3(log 5000=3)で、 は3です.また、 の1つのレベルは、その も い であり、 な である.
3) を めるテクニック
1/nをうまく します.nが になると、1／nは0に かう.
いくつかの ( : )
1) T(n,m)=T 1(n)+T 2(n)=O(max(f(n)、g(m)2) T(n,m)=T 1(n)=T 2(m)=T 2(m)=O(f(n)*g(m))3)の ( は の )が きいO には、 がありますが、T 1(n=n=n=n=n=n=T 1(n=n=n=n=T 1=n=n=n=n=n=T 1=n=n=n=T 1=n=T 1=n=n=n=n=n=n=n=T 1(T 2)の は、T 1(T 1(n=n=T 1(＊f(n)=O(f(n)つまり、 O では、いずれの 0 も じ で、O(1)と されています.4) つの の さと の :c < log2n < n < n*log2n < n^2 < n^3 < 2^n < 3^n < n! （c     ）
|-----------------|-------------|------------------------|   
                                           
もし1つのアルゴリズムの さがc、log 2 n、n、n＊log 2 nであれば、このアルゴリズムの は に く、2 n、3 n、n!ちょっと きいnはこのアルゴリズムが かなくなります. に むいくつかは の に います.
4. 
1)
アルゴリズムの にかかる は、 には できません.テストを しないと かりません.しかし、 たちは アルゴリズムをすべてコンピューターにテストする がないかもしれません.どのアルゴリズムが がかかるかを るだけで、どのアルゴリズムがかかるか が ないだけでいいです.そして、 つのアルゴリズムが やす は、アルゴリズム のステートメントの に しています.どのアルゴリズムの のステートメントが が く、 がかかりますか?アルゴリズム のステートメントの をステートメントの または の と びます.T(n)と す
2)
 に、アルゴリズムの を り し する は、モジュールnのある f(n)であるので、アルゴリズムの は、T(n)＝O(f(n))と される.モジュールnが きくなるにつれて、アルゴリズムが する の はf(n)の に しているので、f(n)が さいほど、アルゴリズムの が くなり、アルゴリズムの が い. の さを する 、まずアルゴリズムの な を し して、それぞれの に づいてその を めて、T(n)の (その は があります. を めると cが られ、 T(n)＝O(f(n))が られます.
3)ありふれた の さ
 ずつ べていくと、ありふれた の さがあります.
 ずつの で、 な の さは、 O(1)、 オーダ(log 2 n)、 O(n)、 オーダ(nlog 2 n)、 オーダ(n^2)、 オーダ(n^3)、…、k オーダ(n^k)、 O(2 n^n)である.ここで、1.O(n)、O(n^2)、 O(n^3)、…、k O(n^k)は であり、それぞれ1 、2 と ぶ.2.O(2^n)は、3. O(log 2 n)であり、 O(nlog 2 n)であり、 の が も い.　　　 ：  ：
　　　  for（i=1;i<=n;++i）
　　　  {
　　　     for(j=1;j<=n;++j)
　　　     {
　　　         c[ i ][ j ]=0; //              ：n^2
　　　          for(k=1;k<=n;++k)
　　　              c[ i ][ j ]+=a[ i ][ k ]*b[ k ][ j ];     
　　　              //             ：n^3
　　　　　　}
　　　  }
          T（n）= n^2+n^3，            ，       n^3 T（n）
　　　　     
         f（n）= n^3，    T（n）/f（n）        c
                  ：T（n）=O（n^3)
5. 
1) の 
 ネストループの を します.たとえば:for (i=1; i<=n; i++)　　    
    x++;　　
for (i=1; i<=n; i++)　　 
   for (j=1; j<=n; j++)
   　　        x++;
 のfor T(n)=nf(n)=n は、Ο(n) のfor T(n)=n 2 f(n)=n 2 は、Ο(n 2)アルゴリズム の は、Ο(n＋n 2)=Ο(n 2)
2) び しの 
たとえば:public void printsum(int count)
{    
    int sum = 1;
    for(int i= 0; isum += i;    }       System.out.print(sum);}
 : な だけが の さを すことを えてください.したがって、 の の は に、 りの の さはO(1)です.したがって、printesmの =forのO(n)+O(1)= =O(n)
ここでは、 num=n*(n+1)/2を いてアルゴリズムを し、public void print＿print＿print sum=1;sum=count*(count+1)/2;System.out.print(sum);というアルゴリズムの が のO(n)からアルゴリズムに されます.
3. ( の の び しと )の 
たとえば:public void suixiangMethod(int n)
{    
    printsum(n);//1.1    
    for(int i= 0; i//1.2    
    }    
    for(int i= 0; ifor(int k=0; kout.print(i,k); //1.3   
    }  
}
suixiangMethod の さは, の のメンバの さを する がある.つまり、1.1+1.2+1.3=O(1)+O(n)+O(n 2)-> と プライマリ =O(n 2)を します.
6.より くの 
1)o(1)  i j       
temp=i;    i=j;    j=temp; 
            1，                 n     
   。            ，  T(n)=O(1)。                n      ，           ，                。           O(1)。
2).O(n^2)sum=0；       /*     1 */
for(i=1;i<=n;i++)         
for(j=1;j<=n;j++)    
sum++；       /*     n2 */
 ：T(n) = 1 + n2 = O(n2)   
for (i=1;i1;        ①  
        for (j=0;j<=(2*n);j++)        
              x++;        ②         
}         
 ：  1    n-1  
  2    (n-1)*(2n+1) = 2n2-n-1   
T(n) = 2n2-n-1+(n-1) = 2n2-2   f(n) = n2   
lim(T(n)/f(n)) = 2 + 2*(1/n2) = 2 
T(n) = O(n2).
3)O(n 3){  
    for(j=0;jfor(k=0;k2;  
    }          
}           
 ： i=m, j=k   ,        k i=m , j    0,1,...,m-1,            0+1+...+m-1=(m-1)m/2   ,i 0  n,        : 0+(1-1)*1/2+...+(n-1)n/2=n(n+1)(n-1)/2 
　　　　　　T(n) = n(n+1)(n-1)/2 = (n^3-n)/2  
　　　　　　f(n) = n^3
        O(n^3)。
7. の さに する な 
アクセス の は 、またはO(1) です. つのアルゴリズムが ステップで のデータ を することができれば、 のように、 はO(log n) を る.strcmpでn の を するとO(n) が です. の アルゴリズムはO(n^3)であり、 はn の を して する があるため、すべての の はn^2である. アルゴリズムは 、 に じてすべての な を めることに する. えば、n の のセットは2 n のサブセットを するので、すべてのサブセットのアルゴリズムはO(2^n)であることが される. アルゴリズムは には、nの が に さい を き、この で を つ すると が になります. なことに、 かに くの があります.( な「 」など)、これまで つけたアルゴリズムは です.もし たちが にこのような に したら、 は に な を めるアルゴリズムで すべきです.
8. に べ えアルゴリズムの の さ
 のページを てください.

両変数の値を他の変数で交換しない3つのアルゴリズム

iphone-センサの使い方と注意事項(距離センサー)