時間計算量と空間計算量

PS：近日、微信公众号の流量主の開通条件が元の 5000 ファンから 500 ファンに引き下げられました。微信のスローガンは「どんなに小さな個体でも自分のブランドを持っている」です。以前に躊躇していた方も、今後の一定期間内に公众号を開通するでしょう。もちろん、腾讯がこのようにするのは、現在の公众号の開封率が非常に低く、百度や头条などの情報流の支配に直面しているため、変わらないわけにはいきません。

時間の複雑さと空間の複雑さは、具体的なプラットフォームに基づいて適切なアルゴリズムを選択するのに役立ちます。空間を時間で交換するか、時間を空間で交換する設計思想を学ぶ必要があります。例えば、マイコンなどでは一般的にメモリ空間が非常に限られているため、最適なアルゴリズムを追求する際には、適切に時間を使って空間を設計することができるべきです。もちろん、大きなメモリデバイスでは、空間を時間で交換する設計思想を選択して最適なアルゴリズムを設計できます。したがって、時間と空間の複雑さは、特定の制約条件の下で、あるアルゴリズムやコードブロックの実行速度を判断する方法として使用できます。主に以下のいくつかの側面から時間と空間の複雑さを理解し、学ぶ必要があります：

データ構造とアルゴリズムの関係
時間の複雑さ
空間の複雑さ
まとめ

データ構造とアルゴリズムの関係#

データ構造は一組のデータの格納構造を指し、アルゴリズムはデータを操作する一連の方法です。したがって、データ構造はアルゴリズムにサービスを提供し、アルゴリズムは特定のデータ構造に作用します。

大 O 複雑度表記法#

大 O 複雑度表記法は、コードの実行時間効率を大まかに理解するのに役立ちます。例えば、以下のコード：

 int cal(int n) {
   int sum = 0;
   int i = 1;
   for (; i <= n; ++i) {
     sum = sum + i;
   }
   return sum;
 }

もし有効なコード（代入操作を含む）の各行の実行時間が 1 単位時間であると仮定すると、上記のコードの実行時間は 2n + 2 単位時間として表すことができます。ここからコードの実行時間は各行の有効コードの実行回数に比例することがわかります。

次のコードの場合：

 int cal(int n) {
   int sum = 0;
   int i = 1;
   int j = 1;
   for (; i <= n; ++i) {
     j = 1;
     for (; j <= n; ++j) {
       sum = sum +  i * j;
     }
   }
 }

仮定条件の下で、上記のコードの実行時間は 2n*n + 2n + 3 として表すことができます。ここでもコードの実行時間は各行の有効コードの実行回数に比例し、公式で表すと：

T(n) = O(n)

したがって、上記の 2 つのコードの実行時間とコード実行回数の関係は次のように表すことができます：

T(n) = O(2n + 2)
T(n) = O( 2n*n + 2n + 3)

データ規模が増大するにつれて、後ろの定数項はコードの実行時間がデータ規模の増加に伴う変化傾向に影響を与えません。上記の 2 つの関数は明らかに 1 つは線形関数で、もう 1 つは二次関数です。n が増加するにつれて、最終的に二次関数の値は一次関数を超えます。したがって、比較のために最高次を取り、他の次の項を除外して簡略化すると次のようになります：

T(n) = O(n)
T(n) = O(n*n)

これで、上記の 2 つのコードの時間の複雑さは大 O 表記法で O (n) と O (n*n) として表すことができます。

時間の複雑さ#

時間の複雑さ：上記の結論から、私たちは大 O 表記法が示すのは、そのコードの実行時間がデータ規模の増加に伴う変化傾向であることを知っています。大 O 表記法の仮定前提は、データ規模の増加に伴い、最高次の項だけを残せばコードの実行時間の複雑さを推定できるということです。したがって、複雑さ分析を行う際には、量級が最も大きい時間の複雑さにのみ注目すればよいです。

一般的な時間の複雑さの量級は小から大へ次のようになります：

定数階(O(1)) < 対数階(O(logn)) < 線形階(n) < 線形対数階(O(nlogn)) < 二次階(O(n^2)) < 三次階(O(n^3)) < 階乗階(O(n!)) < n次方階(O(n^n))

上記の量級の中で、階乗階と次方階は非多項式量級に属します。データ規模が急激に増大する場合、非多項式量級のアルゴリズムの実行時間はますます長くなり、このようなアルゴリズムは最も非効率的なアルゴリズムです。以下に多項式量級の注意点を説明します。

O(n)：コードの行数に関係なく、実行回数だけが確定できる場合、その時間の複雑さの量級は O (1) として表され、O (2)、O (3) などの他の状況は発生しません。

O(logn)：対数時間の複雑さの計算は、満たす条件を見つけ、コードの実行回数を計算することです。つまり、コードが完了するまでに何回実行されるかを見つけることです。以下の例を見てみましょう：

 i=1;
 while (i <= n)  {
   i = i * 2;
 }

上記のコードでは、このコードが何回実行されるかを知るだけでよく、i と n の関係を見つけることです。i の値は順に 1、2、8、16 などであり、つまり 2^0、2^1、2^3、2^4 などです。したがって、i と n の関係は 2^t = n となり、t を計算した後、無関係な項を除外した時間の複雑さは対数時間の複雑さになります。もちろん、線形対数階 **O (nlogn)** は、上記のコードを n 回ループさせた結果です。

O(m+n)：以下のコードのように、複雑さを表すときには、最高次を直接加算することはできません：

int cal(int m, int n) {
  int sum_1 = 0;
  int i = 1;
  for (; i < m; ++i) {
    sum_1 = sum_1 + i;
  }

  int sum_2 = 0;
  int j = 1;
  for (; j < n; ++j) {
    sum_2 = sum_2 + j;
  }

  return sum_1 + sum_2;
}

m と n は 2 つのデータ規模を表し、どちらの量級が大きいかを確定できないため、このときの時間の複雑さは O (m) + O (n) として表されます。もし sum_1 * sum_2 であれば、対応する時間の複雑さは O (m) * O (n) として表されます。

時間の複雑さ分析は基本的に上記のようになります。次に、以下の特殊な状況の複雑さ分析を見ていきます。以下のコードの時間の複雑さを分析します：

// nは配列arrayの長さを表します
int find(int[] array, int n, int x) {
  int i = 0;
  int pos = -1;
  for (; i < n; ++i) {
    if (array[i] == x) pos = i;
  }
  return pos;
}

分析プロセス：i と pos の代入操作は合計 2 回で、コードの実行時間がデータ規模の増加に伴う傾向に影響を与えないため無視できます。for ループ内で、i が m に増加したとき、for ループ内の if 文の条件を満たす場合、このときの時間の複雑さは (1+m) n として表されます。したがって、このコードの時間の複雑さは O (n) です。なぜなら、if 文が x と等しい値を見つけたときでも for ループを終了しないからです。コードを次のように修正します：

// nは配列arrayの長さを表します
int find(int[] array, int n, int x) {
  int i = 0;
  int pos = -1;
  for (; i < n; ++i) {
    if (array[i] == x) {
       pos = i;
       break;
    }
  }
  return pos;
}

もし配列の中で x と等しい値を見つけたらループを終了する場合、このときの時間の複雑さ (1+m) n には 2 つの可能性があります。一つは if 文の条件を満たす値を見つけてループを終了する場合で、このとき m は定数値で無視できます。この場合、このコードの複雑さは O (1) です。もちろん、if 文の条件を満たさないことが知られている場合、ループは n 回続き、この場合の時間の複雑さは O (n) です。このように、同じコードでも異なる条件下では異なる時間の複雑さを持つ可能性があります。このような状況を考慮して、時間の複雑さを 3 つに細分化します：

最良の場合の時間複雑さ分析：理想的な状況で特定のコードを実行する際の複雑さを指します。上記のコードでは、配列の中で if 文の条件を満たす値を見つけたとき、上記のコードの時間の複雑さは O (1) で、最良の時間の複雑さです。
最悪の場合の時間複雑さ分析：最も悪い状況で特定のコードを実行する際の複雑さを指します。上記のコードでは、配列の中で条件を満たす値を永遠に見つけられず、for ループを終了できない場合、このときの時間の複雑さは O (n) で、最悪の時間の複雑さです。

空間の複雑さ#

空間の複雑さは、ストレージスペースがデータ規模の増加に伴う傾向を反映します。以下のコードを見てみましょう：

void print(int n) {
  int i = 0;//スタックメモリ
  int[] a = new int[n];//ヒープメモリ
  for (i; i <n; ++i) {
    a[i] = i * i;
  }
}

上記のコードでは、メモリの申請に関するコードは 2 箇所だけです。変数 i が占めるメモリ空間は固定で無視できますが、配列の宣言はメモリを申請し、そのサイズは n 個の int 型が占めるメモリの大きさです。したがって、このコードの空間の複雑さは O (n) です。

まとめ#

時間の複雑さは、コードの実行時間がデータ規模の増加に伴う変化傾向を反映します。特にループのネストなどに注目します。空間の複雑さは、ストレージスペースがデータ規模の増加に伴う変化傾向を反映します。時間の複雑さは空間の複雑さに比べてより一般的に使用されます。開発者が言う複雑さは、特に指定がない限り、通常は時間の複雑さを指します。さらに、特定のコードに対して、最良の場合の時間の複雑さ、最悪の場合の時間の複雑さ、平均時間の複雑さ、均等時間の複雑さに細分化することができ、分析の思考は基本的に同じですが、制約条件が異なります。