データ構造学習ノート-時間の複雑さ

原文アドレス:データ構造学習ノート-時間複雑度
時間複雑度の定義
アルゴリズム解析を行う場合,文全体の実行回数T(n)は問題規模nに関する関数であり,さらにnに伴うT(n)の変化状況を解析し,T(n)の桁数を決定する.アルゴリズムの時間的複雑度,すなわちアルゴリズムの時間的尺度をT(n)=O(f(n))と記す.問題規模nの増大に伴い,アルゴリズム実行時間の成長率はf(n)の成長率と同じであり,アルゴリズムの漸近時間複雑度と呼ばれ,時間複雑度と略称される.ここでf(n)は問題規模nのある関数である.
このようにアルゴリズムの時間的複雑さを大文字O()で表す記法を大O記法と呼ぶ.
大O次法の導出
アルゴリズムの時間的複雑さをどのように分析しますか?つまりどのようにして大きなO階を導くのでしょうか.以下の導出方法を参考にすることができる.

   O ：
1.    1              。
2.             ，       。
3.            1，            。
        O 。

以下、この導出方法に基づいていくつかの例を見てみましょう.
ていすうステップ

int sum = 0,n = 100;  /*      */
sum = (1 + n) * n/2;  /*      */
System.out.println(sum);  /*      */

このプログラムの実行回数はf(3)である.大きなO次法を用いて,次のように導いた.

定数項3を1に変更します.

は、最上位レベルのアイテムを保持します.

最高次項がないので,このプログラムの時間的複雑度はO(1)である.
このコードの

sum = (1 + n) * n/2;  /*      */

全部で10文ありますが、時間の複雑さはどのくらいですか?
実際,このコードは何文あっても3回と複数回の実行の違いにすぎない.このような実行時間が一定のアルゴリズムを,O(1)を有する時間複雑度,定数次数とも呼ぶ.
注意:この定数がいくらであっても、O(1)と表記します.
同様に,単純分岐構造(ループに含まれないifまたはswitch文)では,実行回数はいずれも一定であり,その時間的複雑度もO(1)である.
線形次数
線形次数のサイクル構造は複雑になります.アルゴリズムの階層を決定するには、特定の文または文セットの実行回数を決定する必要があります.したがって,アルゴリズムの複雑さを解析するには,ループ構造の動作状況を解析することが肝心である.
次のコードは、ループ中のコードがn回実行される必要があるため、ループ時間の複雑さはO(n)である.

for(int i = 0; i < n; i++){
}

たいすうかい

int count = 1;
while(count < n){
    count = count * 2;
}

countに2を乗じるたびにnに近づくからである.すなわち,2乗算後にnより大きいものが何個あるかは,ループを終了する.2^x=nからx=log 2 n(2をベースとするnの対数)が得られる.したがって,このサイクルの時間的複雑度はO(logn)である.
平方階
次の例は、内部サイクル時間の複雑さがO(n)であるサイクルネストである.

int i,j;
for(i = 0; i < n; i++){
    for(j = 0; j < n; j++){
    
    }
}

外部ループについては,この時間複雑度O(n)の文がn回ループしたにすぎないので,このコードの時間複雑度はO(n^2)である.
外部サイクルの回数をmに変更すると,時間複雑度はO(m*n)となる.
したがって,サイクルの時間的複雑さは,サイクルの複雑さにサイクルの実行回数を乗じたものに等しいとまとめることができる.
では、次のコードの時間的複雑さはどのくらいですか.

int i,j;
for(i = 0; i < n; i++){
    for(j = i; j < n; j++){
    
    }
}

i=0のとき,内ループがn回実行されたことを導くことができる.i=1の場合、n−1回、・・・i=n−1の場合、1回実行される.したがって、総実行回数は次のとおりです.
n + (n-1) + (n-2) + …… + 1 = n(n+1)/2 = n^2/2 + n/2
大きいO階の方法を導くことを使います

加算定数がないため、

を考慮しなくてもよい.

は最上位のみを保持する、すなわちn^2/2

を保持する

定数の乗算を除去する、すなわち1/2

を除去する.
最終的に,このコードの時間的複雑さはO(n^2)である.
一般的な時間の複雑さ
この表は、一般的な時間的複雑さをいくつか示しています.
実行回数関数
ステップ
非公式用語
12
O(1)
ていすうステップ
2n+3
O(n)
線形次数
3n^2+2n+1
O(n^2)
平方階
5 log 2 n(2がベースnの対数)+20
O(logn)
たいすうかい
2 n+3 log 2 n(2がベースnの対数)+19
O(nlgon)
nlogn次数
6n^3+2n^2+3n+4
O(n^3)
りっぽうだん
2^n
O(2^n)
インデックス次数
一般的な時間の複雑さは、次のようになります.
O(1)