インタビュアー: アルゴリズムの時間計算量と空間計算量についてどう思いますか?計算方法は？

[[424483]]

1. はじめに

アルゴリズムとは、データを操作し、プログラムの問題を解決するために使用される一連の方法のことです。同じ問題に対して、異なるアルゴリズムを使用すると最終結果は同じになる可能性がありますが、プロセスで消費されるリソースと時間は大きく異なる場合があります。

さまざまなアルゴリズムの利点と欠点は、主に「時間」と「空間」という 2 つの次元を通じて測定されます。

• 時間ディメンション: 現在のアルゴリズムの実行に費やされる時間を指し、通常は「時間複雑度」として表現されます。
• 空間次元: 現在のアルゴリズムを実行するために必要なメモリ領域の量を指します。通常、これを説明するには「空間複雑度」を使用します。

時間と空間の次元を同時に考慮することができない状況に遭遇することが多く、両者のバランスを見つける必要があります。

アルゴリズムには通常、最良、平均、最悪の 3 つのケースがあります。通常は最悪のケースに焦点を当てます。

最悪のケースは、アルゴリズムの実行時間の上限です。一部のアルゴリズムでは、最悪のケースがより頻繁に発生します。つまり、平均的なケースは最悪のケースと同じくらい悪いということです。

2. 時間計算量

時間計算量とは、このアルゴリズムを実行するために必要な計算作業の量を指します。その計算量は、入力サイズが大きくなるにつれてプログラム実行時間の大きさを反映し、アルゴリズムの品質をほぼ反映します。

アルゴリズムにかかる時間は、アルゴリズム内のステートメントが実行される回数に比例します。ステートメントが実行される回数が増えるほど、かかる時間も長くなります。

アルゴリズムの複雑さは通常、ビッグ O 表記法で表され、T(n) = O(f(n)) と定義されます。一般的な時間複雑さには、次の図に示すように、O(1) 定数、O(log n) 対数、O(n) 線形、O(nlogn) 線形対数、O(n^2) 平方、O(n^3) 立方、O(n^k) k 乗、および O(2^n) 指数があります。

上記から、問題のサイズ n が大きくなり続けると、上記の時間計算量も増加し続け、アルゴリズムの実行効率が低下することがわかります。小さい順から大きい順の順序は次のとおりです。

 Ο(1)＜Ο(log n)＜Ο(n)＜Ο(nlog n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2^n)＜Ο(n!)

アルゴリズムの複雑さは、アルゴリズムの成長傾向のみを表し、あるアルゴリズムが必ずしも他のアルゴリズムよりも効率的であることを意味するわけではないことに注意してください。定数項が大きすぎると、アルゴリズムの実行時間も長くなります。

時間の計算量を計算する方法については、次の簡単な例をご覧ください。

関数プロセス(n) {
  a = 1とする
  b = 2とする
  合計をa + bとする
( i = 0; i < n; i++ とします) {
合計+= i
  }
戻る 和 
 }

関数アルゴリズムが実行する必要がある操作の数は、入力サイズnの関数として表されます。つまり、T(n) = 2 + n + 1の場合、時間計算量はO(n + 3)です。時間計算量は最大桁数のみに焦点を当てており、係数とは関係がないため、上記の時間計算量はO(n)です。

たとえば、次の例をご覧ください。

関数プロセス(n) {
 カウントを 0 にする
( i = 0; i < n; i++ とします){
 ( i = 0; i < n; i++ とします){
カウント+= 1
    }
  }
 }

ループの中にネストされたループがあります。外側のループは 1 回実行され、内側のループは n 回実行されるため、時間計算量は O(n*n*1 + 2) = O(n^2) です。

順番に実行されるステートメントの場合、合計時間計算量は、次のように、それらの間の最大時間計算量に等しくなります。

関数プロセス(n) {
  合計を0とする
( i = 0; i < n; i++ とします) {
合計+= i
  }
 ( i = 0; i < n; i++ とします){
 ( i = 0; i < n; i++ とします){
合計+= 1
    }
  }
戻る 和 
 }

最初の部分の複雑さは O(n)、2 番目の部分の複雑さは O(n^2)、合計の複雑さは max(O(n^2), O(n)) = O(n^2) です。

もう一つの例を挙げます。

関数プロセス(n) {
  i = 1; // ①
  (i <= n) の間 {
     i = i * 2; // ②
  }
 }

ループ ステートメントでは、n は 2 の倍数で近似され、そのたびに 2 が乗算されます。これを数式で表すと、1 * 2 * 2 * 2 … * 2 <= nとなり、これは2のx乗がn以下のときにループ本体が実行され、2^x <= nと記録されるので、x<=lognとなる。

したがって、ループはlogn回実行した後に終了するため、時間計算量はO(logn)となる。

同様に、O(n) ループが O(logn) ループ内にネストされている場合、時間の計算量は O(nlogn) です。たとえば、O(n^3) は、O(n) ループの 3 つの層にすぎません。

3. 空間の複雑さ

空間複雑度は主に、アルゴリズムの実行に必要なメモリのサイズを指し、プログラムの実行プロセス中に必要な一時的なストレージ領域を測定するために使用されます。

記憶領域、命令、定数、変数、入力データに加えて、データを操作する作業単位や計算に必要な情報を格納する補助領域も含まれます。

以下は空間計算量が O(1) の例です。

 a = 1とする
b = 2とする
c = 3とする

上記のコードの一時空間はnの変化によって変化しないので、空間計算量はO(1)である。

 arr [] を鳴らす
(i=1; i<=n; ++i)の場合{
  arr.push(i)
 }

上でわかるように、nが増加すると、配列が占めるメモリ空間は大きくなります。

一般的に言えば、アルゴリズムが動的に割り当てられたスペース、再帰、およびスタックに必要なスペースを伴わない限り、スペースの複雑さは通常 O(1) です。1 次元配列 a[n] のスペースの複雑さは O(n) で、2 次元配列のスペースの複雑さは O(n^2) です。

参考文献

• https://juejin.cn/post/6844904167824162823#heading-7
• https://zhuanlan.zhihu.com/p/50479555
• https://cloud.tencent.com/developer/article/1769988