本当の意味での空間の複雑さとは？そして、空間と時間が対立するときのトレードオフとは？
このセクションでは、これら2つの問題に取り組みます。
配列が与えられたら、配列の各要素に2を掛けて返す、というようなアルゴリズムがあります：
private static int[] multi1(int[] array) { int[] newArray = new int[array.length]; for (int i = 0; i < array.length; i++) { newArray[i] = array[i] * 2; } return newArray;}private static int[] multi2(int[] array) { for (int i = 0; i < array.length; i++) { array[i] = array[i] * 2; } return array;}
この2つのアルゴリズムが優れているか劣っているかにかかわらず、それぞれの空間複雑性は何だと思いますか？
最初のアルゴリズムはO(n)の空間複雑度を持ち、2番目のアルゴリズムはO(1)の空間複雑度を持つと言えるかもしれません。
Re！どちらのアルゴリズムも空間の複雑さはO(n)です。
たいていの本や情報源は間違っていますから。
今こそ真の宇宙の複雑さを理解する時です。
このスペースには、入力パラメータと要求された余分なスペースが含まれます。
つまり、上の2つのアルゴリズムでは
- 入力パラメータnと余分な空間nを持つ最初のアルゴリズムは、O(n)の空間複雑度で2nまで加算し、定数項を削除します；
- 2番目のアルゴリズムは、入力パラメータnと余分なスペース0を持つ、O(n)の空間複雑度でnまで加算します。
おわかりのように、空間複雑度を用いてこの2つのアルゴリズムを判断するのは難しいので、別の概念、余分な空間複雑度が生まれました。
アルゴリズムの実行中に要求される余分なスペースです。
上記の2つのアルゴリズムについて、余分な空間の複雑さを使用します：
- 最初のアルゴリズムでは、余分なスペースはnであり、余分なスペースの複雑さはO(n)です；
- 2番目のアルゴリズムでは、余分なスペースは0であり、余分なスペースの複雑さはO(1)です；
O(0)がそのように書かれているのを見たことがないようです。
このように、余分な空間の複雑さを利用することで、2つのアルゴリズムの良し悪しを簡単に決めることができます。
ですから、誤解を正し、今後人とコミュニケーションを取る際には、「余分なスペースの複雑さ」という概念を使うべきでしょう。
多くの小説に書かれているように、時間と空間はしばしば絡み合った概念であり、最終的に主人公は時間と空間の法則を理解し、最強になり、小説は終わります。
データ構造やアルゴリズムにおいても同様で、時間と空間は同時に発生し、しばしば逆方向に動く傾向があります。
例えば、ソートアルゴリズムの場合：
- バブルソート、時間計算量O(n^2)、空間計算量O(1)
- サブサンプションソート、時間計算量O(nlogn)、空間計算量O(n)
つまり、空間のための時間と時間のための空間という2つの考え方があるのです。
では、どちらのアルゴリズムが優れているのでしょうか？
このセクションでは、小さな例から始めて、2つのアルゴリズムの空間複雑性を分析し、空間複雑性の真の本体である余分な空間複雑性を導入し、最後に、バブリングソートとサブサンプションソートの時間複雑性と空間複雑性を比較することによって、空間と時間を交換するアイデアを導きます。
