複雑度分析の概要
一、なぜ複雑度分析が必要なのか#
通常、パフォーマンスを評価するために統計やモニタリングを使用して関連するパフォーマンスデータを取得することがあります。これは「事後分析法」と呼ばれます。
しかし、事後分析法は一般的に存在していますが、いくつかの欠点があります：
- テスト結果はテスト環境に非常に依存しています。
- ある意味では便利ですが、異なるマシンやコンパイル環境に直面すると、同じコードでも異なる結果が得られる場合があります。
- テスト結果はテストのスケールに非常に依存しています。
- 同じコードでも、大規模なスケールと小規模なスケールでは異なる結果が得られます。
では、テスト環境を無視し、どのスケールでもコードのパフォーマンスを比較的正確に分析できる方法はないでしょうか？
もちろんあります。それが「ビッグ O 複雑度表記法」を使用してコードを分析することです。
二、ビッグ O 複雑度表記法#
ビッグ O 表記法：アルゴリズムの時間複雑度は通常、ビッグ O 記号で表され、$T (n) = O\big (f (n)\big)$ と定義されます。関数 $T (n)$ は $f (n)$ に制約されるとも言えます。問題のスケールが n である場合、この問題を解くために必要なアルゴリズムの時間は $T (n)$ です。$T (n)$ はこのアルゴリズムの「時間複雑度」と呼ばれます。入力量 n が増加するにつれて、時間複雑度の極限状態はアルゴリズムの「漸近時間複雑度」と呼ばれます。- 百度百科
時間複雑度#
時間複雑度：完全な名前は「漸近時間複雑度」であり、アルゴリズムの実行時間とデータのスケールの増加の関係を表します。
ここでは、次の式を使用して表します：
| $T(n)$ | $n$ | $f(n)$ | $O$ |
|---|---|---|---|
| コードの実行時間 | コードのスケール | 各行の実行回数 | $T (n)$ は $f (n)$ に比例する |
この式をより理解しやすくするために、例を挙げます：
#include <stdio.h>
int main(){
int c = 0;
for(int i=1; i<=n; ++i)
c += i;
return 0;
}
CPU の視点から見ると、このコードの各行は似たような操作を実行しています：データの読み取り - 演算 - データの書き込み。各行のコードに対応する CPU の実行回数や実行時間は異なるかもしれませんが、ここでは大まかな見積もりを行っているため、各行のコードの実行時間は同じであると仮定できます。この仮定の基に、このコードの総実行時間はどれくらいですか？
3 行目のコードは 1 つの unit_time の実行時間が必要です。4 行目と 5 行目は n 回実行されるため、2n * unit_time の実行時間が必要です。したがって、このコードの総実行時間は (2n+1) * unit_time です。わかるように、すべてのコードの実行時間 T (n) は各行のコードの実行回数に比例します。
時間複雑度の分析方法#
1、最も多くのループ回数を持つコードに焦点を当てる#
ここで重要な推論があります：低次、係数、定数はすべてスケールのサイズに影響を与えないため、$f (n)$ は最高次のみを表す必要があります。
2、加法の法則#
総合複雑度は、最も大きな量級のコードの複雑度です
例を挙げます：
#include <stdio.h>
int main(){
int x=0;
for(int i=1; i<=100; ++i)
x += i;
int y=0;
for(int i=1; i<=n; ++i)
x += i;
int z=0;
for(int i=1; i<=n; ++i){
for(int j=1; j<=n; ++j)
z += j;
}
printf("%d %d %d\n", x, y, z);
return 0;
}
この例では、x、y、z を求めます。それぞれの部分の時間複雑度を求め、最高次を取り、コード全体の複雑度とします。
x を求める部分では、100 回ループします。定数なので無視します。
y を求める部分では、n 回ループします。$O (n)$ とします。
z を求める部分では、$n^2$ 回ループします。$O (n^2)$ とします。
最高次の $O (n^2)$ をコード全体の複雑度とします。
したがって、加法の公式を式で表すと：
3、乗法の法則#
ネストされたコードの複雑度は、ネストされた内外のコードの複雑度の積です
例を挙げます：
#include <stdio.h>
int f(int n);
int main(){
int x = 0;
for(int i=0;i<=n;++i)
x += f(i);
return 0;
}
int f(int n){
int y = 0;
for(int i=0;i<=n;++i)
y += i;
return y;
}
この例では、f () を通常の操作と見なすと、6 行目の時間複雑度は $T_1 (n)=O (n)$ です。しかし、f () は関数であり、その時間複雑度は $T_2 (n)=O (n)$ です。したがって、このコードの時間複雑度は、$T_総 = T_1 (n) * T_2 (n)=O (n*n)=O (n^2)$ です。
一般的な時間複雑度の例#
これらの中で、2 つのカテゴリに分けることができます：多項式オーダーと非多項式オーダー。非多項式オーダーは 2 つだけです：$O (2^n)$ と $O (n!)$。
非多項式オーダーの時間複雑度を持つアルゴリズム問題は、NP 問題と呼ばれます。データのスケール n が増加するにつれて、非多項式オーダーのアルゴリズムの実行時間は急速に増加し、問題の解決時間は無限に増加します。したがって、非多項式時間複雑度のアルゴリズムは非常に効率的ではありません。
1、$O (1)$ - 定数オーダーの時間複雑度#
- この「1」は表現方法の一つです。
コードの実行時間が n の増加に伴って増加しない限り、または、一般的には、ループ文や再帰文が存在しない場合、数千行以上のコードでも、時間複雑度は $O (1)$ です
2、$O (\log n)$、$O (n\log n)$ - 対数オーダーの時間複雑度#
- すべての対数オーダーの時間複雑度を $O (\log n)$ として扱うことができます。同様に、$O (n\log n)$ も同様です。
底の変換公式によると、対数は相互に変換可能です。したがって、任意の対数は $Cf (n)$ に変換できます。そして、先ほど得られた結論によると、定数はコードのスケールに影響を与えないため、無視できます。したがって、対数オーダーの時間複雑度の表現方法では、対数の「底」を無視し、すべて $O (\log n)$ と表記します
3、$O (m+n)$、$O (m*n)$ - 2 つのデータスケールの時間複雑度#
一般的に、2 つのデータのスケールによって決まるコードの複雑度は、どちらが大きいか事前に評価できないため、複雑度を表す際には、単純に加法の法則を利用して片方を省略することはできません。したがって、$O (m+n)$、$O (m*n)$ と表記します。
このような場合、加法の法則は次のようになります：
乗法の法則は変わりません。
空間複雑度の分析#
空間複雑度、正確には漸近空間複雑度は、アルゴリズムのストレージスペースとデータのスケールの増加の関係を表します。
例を挙げます。
#include <stdio.h>
int main(){
int a[n];
for(int i=0; i<=n; ++i)
a[i] = i * i;
for(int i=n-1; i>=0; --i)
pritntf("%d", a[i]);
return 0;
}
このコードを分析すると、3 行目でサイズ n の int 型配列を宣言していますが、それ以外のコードは追加のスペースを占有していません。したがって、コード全体の空間複雑度は $O (n)$ です。
三、まとめ#
複雑度、または漸近複雑度は、アルゴリズムの実行効率とデータのスケールの増加の関係を分析するために使用されます。高次の複雑度のアルゴリズムほど効率が低くなります。一般的な複雑度は多くありません。低次から高次まで、$O (1)$、$O (\log n)$、$O (n)$、$O (n\log n)$、$O (n^2)$ があります。
