さあ、アルゴリズムの複雑さをもう一度理解しましょう!

[[346356]]

0. はじめに

みなさんこんにちは。私は、複数選択パラメータのプログラマーポットです。オペレーティングシステム（主にコンテナ）を「勉強」し、データ構造とアルゴリズム、そして Java を学習している筋金入りの新人です。今日の記事は主にアルゴリズムの時間と空間の複雑さについてお話します。参考資料は主に王正先生のコラム「データ構造とアルゴリズムの美しさ」と昨年の程吉国先生の授業の教材です。

さらに、Cheng Cheng Guo はアルゴリズムに関する github リポジトリを編成しました: https://github.com/DawnGuoDev/algorithm。このリポジトリには、基本的なデータ構造とアルゴリズムの実装に加えて、データ構造とアルゴリズムに関する知識コンテンツ、LeetCode の問題解決記録 (複数のソリューション、Java 実装)、およびいくつかの高品質の書籍も含まれています。

複雑性分析はアルゴリズム学習全体の要であり、これを習得すれば、データ構造とアルゴリズムの内容の半分を習得したことになります。 ”

1. 動機 - 複雑性分析が必要な理由

事後テスト統計手法（つまり、コードを 1 回実行し、統計と監視を通じて実行時間とメモリ サイズを取得する方法）のテスト結果は、テスト環境に大きく依存し、データ規模によって大きく影響されます。しかし実際に必要なのは、特定のテストデータを使用せずにアルゴリズムの実行効率を推定する方法です。

2. Big O 複雑性表現

アルゴリズムの実行効率は、単にアルゴリズムの実行時間です。たとえば、次のコードの実行時間は、各コード行の実行時間が同じであると仮定すると、unit_time になります。この仮定に基づくと、このコードの合計実行時間は (2n + 2) * unit_time になります。

 int cal( int n) {
整数 合計= 0;
整数i = 1;
 (;i <= n; ++i)の場合{
合計=合計+ i;
    }
戻る 合計;
 }

この例から、合計実行時間 T(n) は各コード行の実行回数に比例することがわかります。つまり、式 T(n) = O(f(n)) を満たすことができます。ここで、n はデータのサイズ、f(n) は各コード行の実行回数の合計を表し、O() は関数を表します。つまり、T(n) は f(n) に比例します。この例では、T(n) = O(2n+2) であり、このアプローチは Big O 複雑度表記法と呼ばれます。しかし実際には、Big O の時間計算量は、コード実行の実際の実行時間を具体的に示すものではなく、むしろデータ規模の拡大に伴うコード実行時間の変化傾向を示しており、漸近的時間計算量、または単に時間計算量とも呼ばれます。そして、式2n+2において、係数2と定数2は成長傾向に影響を与えません。例えば、それは線形であり、その線形成長傾向は係数2や定数2によって変化しません。したがって、T(n)=O(n)と書くこともできます。たとえば、T(n) = O(n^2) は、コード実行時間がデータ サイズ n とともに n の 2 乗の割合で増加することを意味します。次の図は、データ サイズが増加するにつれて、さまざまな時間複雑度の実行時間がどのように変化するかを示しています。

3. 時間計算量分析

コードの時間計算量を分析するにはどうすればよいでしょうか？使用できる方法はいくつかあります

• ループが最も多いコードセクションのみに焦点を当てる

Big O 複雑性表現は傾向のみを示すため、数式内の定数項、低次数、係数などを無視し、最大の大きさのみを記録できます。したがって、アルゴリズムまたはコードの複雑さを分析するときは、ループの数が最も多いコード部分に注目するだけで済みます。例えば、次のコードの時間計算量はO(n)です。

 int cal( int n) {
整数 合計= 0;
整数i = 1;
 (;i <= n; ++i)の場合{
合計=合計+ i;
    }
戻る 合計;
 }

• 追加ルール: 全体の複雑さは、最大のコードセグメントの複雑さに等しい

これは主に、ビッグ O 複雑度の低次の項を省略するためです。個人的には、この方法は上記の方法と多少重複していると感じています。例えば、次のコードはループに応じて 3 つのセクションに分けることができます。最初のセクションにはループがありますが、ループの数は定数項であり、成長傾向に影響を与えません。したがって、時間計算量は O(1) です。コードの 2 番目のセクションの時間計算量は O(n)、コードの 3 番目のセクションの時間計算量は O(n^2) です。これら 3 つのセグメントの中で最大の時間計算量は、コード全体の時間計算量でもあります。

 int cal( int n) {
整数sum_1 = 0;
整数p = 1;
 ( ; p < 100; ++p) {
        合計1 = 合計1 + p;
    } 
 
整数sum_2 = 0;
整数q = 1;
 (; q < n; ++q)の場合{
        合計2 = 合計2 + q;
    } 
 
整数sum_3 = 0;
整数i = 1;
整数j = 1;
 (; i <= n; ++i)の場合{
        1 = 1;
 (; j <= n; ++j)の場合{
            合計3 = 合計3 + i * j;
        }
    } 
 
 sum_1 + sum_2 + sum_3 を返します。
 }

• 乗算ルール: ネストされたコードの複雑さは、ネストされたコードの内側と外側のコードの複雑さの積に等しい。

たとえば、次のコードでは、f() は全体の複雑度が O(n) のループ演算です。cal() のループは、f() を呼び出す外側の層に相当します。f() を単純な演算と見なすと、時間の複雑度は O(n) です。f() の実際の複雑度を考慮すると、cal() 全体の時間の複雑度は O(n)*O(n)=O(n*n) = O(n^2) になります。

 int cal( int n) {
戻り値:
整数i = 1;
 (; i < n; ++i)の場合{
        ret = ret + f(i);
    }
 } 
 
 int f( int n) {
整数 合計= 0;
整数i = 1;
 (; i < n; ++i)の場合{
合計=合計+ i;
    }
戻る 合計;
 }

3.1. 共通の時間計算量

上記の時間的複雑さについての説明は次のとおりです。

1.O(1)

O(1) は、一定の時間計算量を表します。コードの時間が n の増加に伴って増加しない限り、その時間計算量も O(1) です。一般的に言えば、アルゴリズムにループ文や再帰文がない限り、コード行が数千行あっても時間の計算量は O(1) です。

2. O(logn)、O(nlogn)

対数時間計算量は解析が難しい場合が多い。例えば、次のコードでは

私 = 1;
 (i <= n) の間 {
    私 = 私 * 2;
 }

私 = 1;
 (i <= n) の間 {
    i = i * 3;
 }

O(nlogn) の時間計算量は、上記の「乗算規則」と同等です。つまり、コードの時間の計算量は O(logn) であり、このコードが n 回ループされると、時間の計算量は O(nlogn) になります。

3. O(m+n)、O(m*n)

この場合、コードの複雑さは 2 つのデータのサイズによって決まります。次のコードに示すように:

 int cal( int m, int n) {
整数sum_1 = 0;
整数i = 1;
 (; i < m; ++i)の場合{
        合計1 = 合計1 + i;
    } 
 
整数sum_2 = 0;
整数j = 1;
 (; j < n; ++j)の場合{
        合計2 = 合計2 + j;
    } 
 
 sum_1 + sum_2を返します。
 }

このコードから、m と n は 2 つのデータ スケールであり、m と n の大きさは評価できないことがわかります。したがって、いずれも省略できないため、O(m+n) となります。

4. O(2^n)、O(n!)

上記の表に記載されている複雑さのレベルは、大まかに多項式レベルと非多項式レベルの 2 つのカテゴリに分類できます。これらは、多項式ではない唯一の 2 つの大きさです。非多項式規模のアルゴリズムの問​​題は、NP (非決定性多項式) 問題とも呼ばれます。 n がどんどん大きくなると、非多項式スケールアルゴリズムの実行時間が大幅に増加し、問題を解くための実行時間も無限に増加するため、非常に非効率的なアルゴリズムになります。

3.2. 最良および最悪の場合の時間計算量

たとえば、次のコードでは、配列内のデータが検索されますが、途中でデータが見つかり、ループを早期に終了する可能性があるため、配列全体が走査されるわけではありません。最良のケースは、配列の最初の要素が検索対象の変数 x である場合、時間の計算量は O(1) です。最悪のケースは、配列全体を走査しても目的の x が見つからない場合であり、その場合、時間の計算量は O(n) になります。したがって、O(1) はこのコードの最良のケースの時間計算量、つまり最良のケースでこのコードを実行する時間の計算量です。 O(n) はこのコードの最悪のケースの時間計算量です。

 // nは配列の長さを表します
int find( int [] 配列, int n, int x) {
整数i = 0;
整数位置 = -1;
 (; i < n; ++i)の場合{
        （配列[i] == x）の場合{
            位置 = i;
            壊す;
        }
    }
位置を返します。
 }

3.3. 平均ケース時間計算量（加重平均時間計算量または期待時間計算量）

最良および最悪のケースの時間複雑度は、まれにしか発生しない極端な状況の時間複雑度です。したがって、平均的なケースの時間計算量を使用してそれを表現できます。たとえば、上記のコードでは、配列内の x の位置を検索するときに、配列内にある状況と配列内にない状況の 2 つの状況があります。配列では、配列内の位置 0 ～ n-1 に配置できます。配列内にある確率と配列内にない確率がそれぞれ 1/2 であり、配列内の位置 0 ～ n-1 の確率が同じで、1/(2 * n) であると仮定します。したがって、上記セクションの平均時間計算量（または加重平均時間計算量、期待時間計算量）は

複雑度を次の式で計算すると、各状況が発生する確率は 1/(n+1) に相当します。これは、各状況の異なる確率を考慮していないため、ある程度の不正確さがあります。

3.4. 償却時間計算量

償却時間計算量は償却解析法（償却解析法）を使用します。つまり、時間のかかる操作を、時間のかかる複雑度が低い他の操作に分散します。例えば次のコード

// 配列は長さ n の配列を表します
// コード内のarray.lengthはnに等しい
int [] 配列 = 新しいint [n];
整数 カウント= 0; 
 
 void挿入( int値 ) {
    if ( count == array.length) {
整数 合計= 0;
 ( int i = 0; i < 配列の長さ; ++i) {
合計=合計+ 配列[i];
        }
        配列[0] =合計;
カウント= 1;
    } 
 
    配列[ count ] = val;
    ++カウント;
 }

このコードが実現したいのは、配列にデータを挿入することです。配列がいっぱいの場合、合計は配列の最初の位置に配置され、その後、データが配列に挿入され続けます。分析により、このコードの最良のケースの時間計算量は O(1)、最悪のケースの時間計算量は O(n)、平均時間計算量は O(1) であることがわかります。

このコードでは、ほとんどの場合、時間の計算量は O(1) であり、一部のケースでのみ計算量が O(n) になります。さらに、O(1) と O(n) は比較的規則的なパターンで現れます。通常、1 回の O(n) 実行の後には、n-1 回の O(1) 実行が行われます。このような状況では、償却分析法を使用できます。これは、O(n) の時間計算量を次の n-1 回の O(1) 実行に償却するものです。償却時間計算量は O(1) であり、これは償却時間計算量です。

償却時間の計算量はあまり一般的ではありません。一般的なシナリオは、データ構造に対して一連の連続操作を実行することです。ほとんどの場合、時間の計算量は非常に低く、時間の計算量が比較的高いのは一部の場合のみです。さらに、これらの操作の間には一貫した時間的関係があります。たとえば、前述のように、最初に O(1) 時間計算量の一連の操作があり、その後に O(n) 時間計算量の操作が続きます。このとき、償却分析法を使用して、時間複雑度の高い操作で消費された時間を、時間複雑度が低い他の操作に分散することができます。

一般に、償却時間の計算量は、最良のケースの時間計算量と等しくなります。では、平均時間計算量と償却時間計算量をどのように区別するのでしょうか。使用する方法によって異なると思います。償却分析法を使用して計算された時間計算量が償却時間計算量である場合、重み付け法または期待値計算法を使用して計算された時間計算量は平均時間計算量です。

4. 空間複雑性分析

空間複雑度解析方法は非常にシンプルです。時間計算量の正式名称は漸近的時間計算量であり、アルゴリズムの実行時間とデータのサイズの間の増加関係を示します。空間計算量の正式名称は漸近空間計算量であり、アルゴリズムの記憶領域とデータ規模の増加関係を示します。

たとえば、次のコードでは、まず int i = 0; が変数を格納するためのスペースを割り当てます。変数は定数なので無視できます。Int[] a = new int[n]; はサイズ n の int 型配列を割り当てます。コードの残りの部分はそれ以上のスペースを占有しないため、スペースの複雑さは O(n) です。

 void print( int n) {
整数i = 0;
 int [] a = 新しいint [n];
 (i; i < n; ++i)の場合{
        関数はa[i]とb[i]の2つから成ります。
    } 
 
 (i = n-1; i >= 0; --i)の場合{  
        a[i]を印刷する
    }
 }

スペースの複雑さの分析は、実際には非常に簡単です。一般的には、変数を宣言するときに割り当てられたスペースのサイズを確認するだけで済みます。

4.1. 共通の時間計算量

上記の 3 種類の空間計算量は一般的に使用されます。O(nlogn) や O(logn) などの対数計算量は一般的に使用されません。

5. 結論

複雑性分析を振り返ると、一般的に、時間複雑性の動機は、特定のデータを使用せずにアルゴリズムの実行効率を推定できる方法を求めることです。時間の複雑さは Big O 表記法で表現され、実際には成長傾向を表します。たとえば、n^2 では、n の値がどんどん大きくなると、O(n^2) アルゴリズムの実行時間は 2 乗的に増加しますが、O(n) アルゴリズムの実行時間は線形的に増加します。したがって、O(n^2) の時間計算量は高くなります (最初の図を参照)。次に、平均時間複雑度、最良および最悪の時間複雑度、償却時間複雑度など、一般的に使用される時間複雑度がいくつかあります（償却の考え方は、ある程度オペレーティングシステムに反映されています。RRスケジューリングアルゴリズムでは、タイムスライスサイズを選択するための同様の処理方法があります。RRはプリエンプティブスケジューリングアルゴリズムであるためです。スケジューリングが発生すると、プロセスのコンテキストスイッチが発生し、プロセスのコンテキストスイッチには追加の時間コストが必要になり、この時間コストはタイムスライスに償却されます。タイムスライスが大きい場合、償却効果は明ら​​かに良いので、この追加の時間コストの影響は小さくなります）。

なぜ時間計算量をマスターすることが基本的な方法をマスターすることだと言われるのでしょうか？昨年の授業で最もはっきり覚えているのは、先生がより難しいアルゴリズムの問​​題について話しているようで、次に最も単純で最も複雑な解決策から始めて、各コード部分の時間計算量を段階的に分析するように導き、次に「このコードの時間計算量はO(n^2)ですが、それを減らす方法は見つかりますか？」と言ったことです。そして、それを減らす方法を考え、コードを一つずつ見て、絵を描くなどして、最終的に時間計算量を減らしました。したがって、個人的には、時間計算量分析を習得した後は、アルゴリズムの分析方法を習得したと考えています。各コードの複雑さを分析し、思考を通じて対応するコードの時間計算量を削減できます。複雑性分析に精通していないと、複雑性を削減する方法がわからず、アルゴリズムの最適化も行われません。

この記事はWeChatパブリックアカウント「Multi-Select Parameters」から転載したものです。以下のQRコードからフォローできます。この記事を転載する場合は、Multi-Select Parameters の公開アカウントにご連絡ください。