複雑度分析の浅析
一、なぜ複雑度分析が必要なのか#
通常、統計やモニタリングを通じて、関連するパフォーマンスデータを取得してパフォーマンスを評価することがあります。これは「事後分析法」と呼ばれます。
しかし、事後分析法は一般的に存在していますが、いくつかの欠点があります：
- テスト結果はテスト環境に非常に依存しています。
- ある意味では便利ですが、異なるマシンやコンパイル環境に直面すると、同じコードでも異なる結果が得られる場合があります。
- テスト結果はテストのスケールに非常に依存しています。
- 同じコードでも、大規模な場合と小規模な場合では異なる結果が得られます。
では、テスト環境を無視して、どのスケールでもコードのパフォーマンスを比較的正確に分析できる方法はないでしょうか？
もちろんあります。それは「ビッグ 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 つのカテゴリに分けることができます：多項式オーダーと非多項式オーダー。非多項式オーダーは $O (2^n)$ と $O (n!)$ の 2 つだけです。
非多項式オーダーの時間複雑度を持つアルゴリズム問題を 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)$ があります。
