アルゴリズムの学習に不可欠な時間計算量と空間計算量、あなたはどれくらい知っていますか?

[[373785]]

この記事はWeChatの公開アカウント「Programming New Vision」から転載したもので、著者はUgly Fat Man Second Brotherです。記事の転載については、Program New Visionの公式アカウントまでご連絡ください。

序文

アルゴリズムとは、データを操作し、プログラムの問題を解決するために使用される一連の方法のことです。アルゴリズムは大企業や外資系企業の面接では必須であり、上級プログラマーにとっても必要なスキルです。同じ問題を解決するために使用できるアルゴリズムは多数ありますが、アルゴリズムが異なれば効率やストレージスペースが大きく異なる場合があります。

では、アルゴリズムの長所と短所を測定するためにどのような指標が使用されるのでしょうか。その中で、前述の効率性はアルゴリズムの時間複雑度によって説明でき、占有されるストレージスペースはアルゴリズムの空間複雑度によって説明できます。

• 時間の複雑さ: プログラムの実行に費やされる時間を評価するのに使用され、プログラムがプロセッサを使用する程度を推定できます。
• 空間複雑度: 実行中のプログラムが占有するメモリ空間を評価するために使用され、プログラムのコンピュータメモリ使用度を推定できます。

実践や面接では、特定のアルゴリズムを記述できるだけでなく、アルゴリズムの長所と短所を評価できるように、アルゴリズムの時間計算量と空間計算量を理解する必要があります。時間の計算量と空間の計算量を同時に満たすことができない場合は、バランスポイントを選択する必要があります。

アルゴリズムには通常、最良、平均、最悪の 3 つのシナリオがあります。通常は最悪のシナリオに焦点を当てます。最悪のケースは、アルゴリズムの実行時間の上限です。一部のアルゴリズムでは、最悪のケースがより頻繁に発生します。つまり、平均的なケースは最悪のケースと同じくらい悪いということです。

一般的に、時間計算量は空間計算量よりも問題が発生しやすいため、時間計算量に関する研究が多く行われています。面接で特に指定がない限り、時間計算量についても議論されます。

時間計算量

アルゴリズムの時間計算量を取得するには、アルゴリズム プログラムを 1 回実行してみるのが最も直感的な方法です。そうすれば、自然に取得できます。しかし、実際には、テスト環境やデータサイズなどの要因により、アルゴリズムを直接テストすることは実装が困難であったり、エラーが大きくなったりします。理論的には、すべてのアルゴリズムをテストする必要はありません。アルゴリズムの実行に費やされた時間の基本的な傾向を取得するための評価指標を見つけるだけで十分です。

時間周波数

一般的に、アルゴリズムにかかる時間は、コード ステートメントが実行される回数に比例します。アルゴリズムが実行するステートメントの数が増えるほど、消費される時間も長くなります。アルゴリズム内のステートメントが実行される回数を時間頻度と呼び、T(n) で表されます。

漸近的時間計算量

時間周波数 T(n) において、n は問題の規模を表します。n が変化すると、T(n) もそれに応じて変化します。したがって、n が変化すると T(n) がどのようなパターンを示すかを知りたい場合は、時間計算量の概念を導入する必要があります。

一般に、アルゴリズムの基本操作の繰り返し回数は問題のサイズ n の関数であり、時間周波数 T(n) として表されます。 n が無限大に近づくときに T(n)/f(n) の極限値がゼロ以外の定数となるような関数 f(n) が存在する場合、f(n) は T(n) と同じ桁数の関数となり、T(n)=O(f(n)) と表され、O(f(n)) はアルゴリズムの漸近的時間計算量、または単に時間計算量と呼ばれます。

漸近的な時間計算量は大文字の O で表されるため、Big O 表記法とも呼ばれます。アルゴリズムの時間計算量関数は、T(n)=O(f(n)) です。

T(n)=O(f(n))は、nが正の無限大に近づくときにT(n)≤C*f(n)となる定数Cが存在することを意味します。簡単に言えば、n が正の無限大に近づくと、T(n) は最大値に達し、これは f(n) とほぼ同じになります。つまり、nが正の無限大に近づくと、T(n)の上限はC * f(n)になります。 f(n) に関する規定はありませんが、一般的には可能な限り単純な関数として使用されます。

一般的な時間計算量には、O(1)定数型、O(log n)対数型、O(n)線形型、O(nlog n)線形対数型、O(n2)平方型、O(n3)立方型、O(nk)k乗型、およびO(2n)指数型があります。

上図は、さまざまなタイプの関数の成長傾向を示しています。問題の規模 n が増加し続けると、上記の時間計算量も増加し続け、アルゴリズムの実行効率は低下します。

一般的なアルゴリズムの時間計算量は小さいものから大きいものの順に、Ο(1)<Ο(log n)<Ο(n)<Ο(nlog n)<Ο(n2)<Ο(n3)<…<Ο(2^n)<Ο(n!)となります。

アルゴリズムの複雑さはアルゴリズムの成長傾向を示すだけであり、あるアルゴリズムが必ずしも他のアルゴリズムよりも効率的であるとは言えないことに注意してください。これには、問題サイズ n の範囲を追加する必要があります。問題の仕様が特定の範囲に達するまでは、1 つのアルゴリズムが別のアルゴリズムよりも効率的ですが、しきい値を超えると、状況が逆になる可能性があります。これは、上の図から明確にわかります。このため、実際に得られる結論は、上記のアルゴリズムの順序とは逆になる可能性があります。

時間計算量を推定する方法

上記では、時間計算量の基本的な概念と表現について学びました。では、実際にコードを通じて対応する表現を取得するにはどうすればよいでしょうか。これには、アルゴリズムの複雑さを解決することが含まれます。

アルゴリズムの複雑さを解決するには、通常、次の手順に分けられます。

• アルゴリズム内の基本ステートメントを見つけます。アルゴリズム内で最も多く実行されるステートメントは基本ステートメントであり、通常は最も内側のループのループ本体です。
• 基本ステートメントの実行回数の桁数を計算します。基本ステートメントの実行回数の桁数を計算するだけで済みます。つまり、関数内の最高乗数が正しい限り、すべての低乗数と最高乗数の係数を無視できます。これにより、アルゴリズムの分析が簡素化され、最も重要な点である成長率に集中できるようになります。
• アルゴリズムの時間パフォーマンスを表現するには、big O を使用します。つまり、基本ステートメントが実行される回数の大きさの順序を big O 表記で表します。

Big O 表記法を使用する場合、通常、次の 3 つのルールがあります。

• ランタイム内のすべての加算定数を定数 1 に置き換えます。
• 時間関数の最高次の項のみが保持されます。
• 最高次の項が存在する場合、最高次の項の前の係数は省略されます。

上記の推論手順とルールを具体的な例を通して以下に説明します。

時間計算量の例

定数次数 O(1)

実行されるコード行数に関係なく、ループなどの複雑な構造がない限り、このコードの時間計算量は O(1) です。

整数i = 1;
整数j = 2;
整数k = 1 + 2;

上記のコードを実行すると、各ステートメントの頻度は 1 となり、問題のサイズ n が変化しても変化しません。したがって、アルゴリズムの時間計算量は定数であり、T(n)=O(1)と表されます。ここで注意する必要があるのは、上記のコードが数千行であっても、アルゴリズムの実行時間が問題のサイズ n の増加に伴って増加しない限り、実行時間は比較的大きな定数であるということです。このようなアルゴリズムの時間計算量はO(1)です。

対数順序 O(log n)

まず、対応するサンプルコードを見てみましょう。

 int i = 1; // ①
 (i <= n) の間 {
   i = i * 2; // ②
 }

上記コードでは、文①の頻度は1ですが、無視できます。

文②から、nを2の倍数で近似し、そのたびに2を掛けていることがわかります。数式で表現すると、122*2…*2 <=n となり、2 の x 乗が n 以下のときにループ本体が実行され、2^x <= n と記録されるため、x<=logn となります。つまり、上記のループは logn 回実行した後に終了するため、上記のコードの時間計算量は O(log n) になります。

実際、上記のコードの時間計算量の式は正確には T(n) = 1 + O(log n) となるはずですが、対応する原則「時間関数では最上位の項のみを保持する」についてはすでに上で述べたので、O(log n) として記録されます。

線形順序 O(n)

サンプルコード:

 int j = 0; // ①
 for ( int i = 0; i < n; i++) { // ②
   j = i; // ③
   j++; // ④
 }

上記コードでは、文①の頻度は1、文②の頻度はn、文③の頻度はn-1、文④の頻度はn-1なので、アルゴリズム全体はT(n)=1+n+(n-1)+(n-1)という式で表すことができます。さらに、T(n)=1+n+(n-1)+(n-1)=3n-1、つまり O(n)=3n-1 と推測できます。低次の累乗と係数を除去すると、O(n)=n となり、T(n)=O(n) となります。

上記のコードでは、for ループ内のコードは n 回実行されるため、消費時間は n の変化に応じて直線的に変化します。したがって、このタイプのアルゴリズムの時間計算量は O(n) として表すことができます。

線形対数順序 O(nlogN)

サンプルコード:

 ( int m = 1; m < n; m++)の場合{
 int i = 1; // ①
   (i <= n) の間 {
      i = i * 2; // ②
   }
 }

線形対数順序は、対数順序 O(log n) と対比して理解する必要があります。上記コードの for ループ内のコードは、前述の対数順序ですが、対数順序の外側に n 回ループがあります。もちろん、その時間計算量は n*O(log n) なので、O(nlog n) と記録されます。

平方順序 O(n²)

サンプルコード:

整数k = 0;
 ( int i = 0; i < n; i++)の場合{
 ( int j = 0; j < n; j++)の場合{
      関数
   }
 }

平方順序は線形順序と対比して理解できます。線形順序は for ループのレイヤーであり、O(n) と表記されます。この時点で、これはネストされた別の for ループのレイヤーと同等であり、n * O(n)、つまり O(n * n)、または O(n^2) になります。

外側のループの n が m に変更されると、次のようになります。

整数k = 0;
 ( int i = 0; i < m; i++) {
 ( int j = 0; j < n; j++)の場合{
      関数
   }
 }

すると、対応する時間計算量は O(m * n) になります。

同様に、3次順序 O(n³) と K 次順序 O(n^k) は、3 層のループと k 層のループがネストされただけです。

ソートアルゴリズムの比較

上記では、さまざまなアルゴリズム例の時間計算量推論プロセスを紹介しました。上記の時間計算量とアルゴリズムの効率を比較しながら、いくつかの一般的なソートアルゴリズムの時間計算量の比較を見てみましょう。

空間の複雑さ

最後に、空間の複雑さについて見てみましょう。空間複雑度は主に、アルゴリズムを実行するために必要なメモリのサイズを指します。プログラムの実行プロセス中に必要な一時的なストレージ スペースを測定するために使用されます。ここでの空間複雑度も推定されます。

プログラム実行には、記憶領域、命令、定数、変数、入力データに加えて、データを操作する作業単位と、計算に必要な情報を格納するための補助領域も含まれます。ストレージ空間には通常、命令空間 (つまりコード空間)、データ空間 (定数、単純な変数) などが占める固定部分と、動的割り当てと再帰スタックに必要な変数空間が含まれます。変数空間はアルゴリズムに関連しています。

アルゴリズムに必要な記憶領域はf(n)で表されます。 S(n)=O(f(n)) ここでnは問題のサイズ、S(n)は空間の複雑さを表します。

空間計算量の一般的な例を 2 つ、空間計算量 O(1) と O(n) を見てみましょう。

空間計算量 O(1)

空間計算量が O(1) の場合のサンプルコードは、時間計算量が O(1) の場合のサンプルコードと同じです。

整数i = 1;
整数j = 2;
整数k = 1 + 2;

上記のコードでは、一時領域はnの変化によって変化しないため、空間計算量はO(1)です。要約すると、アルゴリズムの実行に必要な一時スペースが変数 n のサイズによって変化しない場合、このアルゴリズムのスペース計算量は定数であり、O(1)、つまり S(n) = O(1) として表すことができます。

空間計算量 O(n)

サンプルコード:

整数j = 0;
 int [] m = 新しいint [n];
 ( int i = 1; i <= n; ++i)の場合{
   j = i;
   j++;
 }

上記のコードでは、int 配列を作成するためのスペースの割り当てのみが n のサイズに関連し、for ループでは新しいスペースは割り当てられません。したがって、対応するスペースの複雑さは S(n) = O(n) です。

総括する

この記事では、アルゴリズムの長所と短所は時間計算量と空間計算量によって測定できることを説明し、具体的な例を使用して、さまざまな方法の時間計算量と空間計算量を計算する方法を説明します。これらの基本的な概念、機能、計算方法、計算規則、アルゴリズムのパフォーマンスを理解すれば、アルゴリズムを研究することで、アルゴリズムのパフォーマンスやその他の指標を簡単に推定できます。

参考文献:

https://blog.csdn.net/zolalad/article/details/11848739

https://zhuanlan.zhihu.com/p/50479555