プログラムの時間複雑度はどう計算しますか?

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

Temp=i;i=j;j=temp;                    

以上の3つの単語句の頻度はいずれも1であり、このプログラムの実行時間は問題規模nに関係ない定数である.アルゴリズムの時間複雑さは定数次数であり,T(n)＝O(1)と記した.アルゴリズムの実行時間が問題規模nの増加とともに増加しない場合、アルゴリズムに千個以上の語句があっても、その実行時間は大きな定数にすぎない.このようなアルゴリズムの時間複雑さはO(1)である.
O(n^2)
2.1. iとjの内容を交換する

sum=0；                 （  ）
for(i=1;i<=n;i++)       （n  ）
for(j=1;j<=n;j++)（n^2  ）
sum++；       （n^2  ）
 ：T(n)=2n^2+n+1 =O(n^2)

2.2.

for (i=1;ii++) {
    y=y+1;         ①   
    for
    (j=0;j<=(2*n);j++)    
    x++;        ②      
}   

正解: 語句1の頻度はn-1です. 語句2の頻度は(n-1)*(2 n+1)=2 n^2-n-1 f(n)=2 n^2-n-1+(n-1)=2 n^2-2 このプログラムの時間複雑度T(n)=O(n^2)
O(n)
2.3.

a=0;
b=1;                      ①
for(i=1;i<=n;i++){ ②  
    s=a+b;　　　　③
    b=a;　　　　　④  
    a=s;　　　　　⑤
}

語句1の頻度:2、 語句2の頻度:n、 語句3の頻度:n-1、 語句4の頻度:n-1、 語句5の頻度:n-1、 T(n)=2+n+3(n-1)=4 n-1=O(n)
O(ロゴ2 n) 2.4.

i=1;       ①
while (i<=n)
    i=i*2; ②

語句1の頻度は1で、 設定語句2の頻度はf(n)で、2^f(n)<=n;f(n)<=log 2 n 最大値f(n)=log 2 n,T(n)=O(log 2 n)をとります.
O(n^3)
2.5.

    for(i=0;ii++)
    {  
       for(j=0;j0;k2;  
       }
    }

i=mとすると、 j=kの場合、内層サイクルの回数はk=mの場合、jは0,1,m-1を取ることができます.m-1ですので、ここでは一番内側のサイクルは0+1+1+…+m-1=(m-1)m/2回が行われます.
アルゴリズムの最悪の場合の挙動と期待挙動も区別しなければならない.クイックソートの最悪の場合、運転時間はO(n^2)ですが、期待時間はO(nlogn)です.毎回基準値を慎重に選択することによって、二乗の場合(すなわちO(n^2)の確率をほぼ0に低減することができる.実際には、念入りに実現されたクイックソートは、一般的に(O(nlogn)時間で実行されます.
以下はよく使う覚え方です. アクセス配列の要素は定数時間動作、またはO(1)動作です.一つのアルゴリズムは、各ステップで半分のデータ要素を削除できます.例えば、二分検索では、O(logn)時間をとります.2つのn文字の列をstrcmpで比較すると、O(n)時間が必要です.従来のマトリックス乗アルゴリズムはO(n^3)です.要素ごとにnを乗算して加算する必要があるので、すべての要素の個数はn^2です. 指数時間アルゴリズムは、一般的にすべての可能な結果を求める必要があるからです.例えば、n個の要素のセットは2 nのサブセットを共有しています.したがって、すべてのサブセットのアルゴリズムはO(2 n)になります.指数アルゴリズムは、一般的には、nの値が非常に小さい場合を除いて、この問題で要素を一つ追加すると、動作時間が倍になります.残念なことに、多くの問題があります.(有名な「巡回販売員問題」など)、これまで見つけたアルゴリズムはすべて指数です.もし私たちが本当にこのような状況に遭遇したら、最適な結果に近いアルゴリズムで代替すべきです.
計算方法
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(^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)