データ構造における時間計算量と空間計算量の基礎

アルゴリズム解析とは

アルゴリズムの効率性の分析は、実装前と実装後という2つの異なる段階で行うことができます。

事前解析(ア・プリオリ解析) − これはアルゴリズムの理論的な分析を指します。プロセッサの速度など、他のすべての要素は一定であり、実装結果に影響を与えないものと仮定したうえで、アルゴリズムの効率性を測定します。

事後解析(ア・ポステリオリ解析) − これはアルゴリズムの経験的(実証的)な分析を指します。選択したアルゴリズムを実際にプログラミング言語で実装し、対象となるコンピュータ上で実行します。この段階では、実行時間や必要なメモリ容量といった実際の統計データが収集されます。

アルゴリズム解析では、処理に含まれるさまざまな操作の実行時間(ランニングタイム)を扱います。ある操作の実行時間は、「その操作あたりに実行されるコンピュータ命令の数」として定義できます。

アルゴリズムの計算量(Complexity)

X をアルゴリズム、N を入力データのサイズとすると、アルゴリズム X が消費する「時間」と「空間」は、X の効率性を決める2大要素となります。

時間要因 − 時間は、ソートアルゴリズムにおける比較回数のような主要な操作(キー操作)の回数を数えることで測定されます。

空間要因 − 空間は、アルゴリズムが必要とする最大メモリ容量を数えることで測定されます。

アルゴリズムの計算量 f(N) とは、入力データのサイズ N に対して、そのアルゴリズムの実行時間および/または必要な記憶領域を示す指標です。

空間計算量(Space Complexity)

アルゴリズムの空間計算量とは、そのアルゴリズムがライフサイクル全体を通じて必要とするメモリ空間の量を表すものです。

アルゴリズムが必要とする空間は、次の2つの要素の合計で構成されます。

• 固定部分: 単純な変数や定数、プログラムサイズなど、問題の規模に依存しないデータを格納するために必要な空間。
• 可変部分: 再帰呼び出しのスタック領域や動的メモリ確保など、そのサイズが問題の規模に完全に依存する変数に必要な空間。

任意のアルゴリズム p の空間計算量 S(p) は、次の式で表されます。

S(p) = A + Sp(I)

ここで、A は固定部分、Sp(I) はインスタンス特性 I に依存する可変部分です。以下に、この概念を説明する簡単な例を示します。

アルゴリズム例

SUM(P, Q)
Step 1 - START
Step 2 - R ← P + Q + 10
Step 3 - Stop

この例では、3つの変数(P、Q、R)と1つの定数が使われています。したがって、S(p) = 1 + 3 となります。実際に必要な空間は、これらの定数や変数のデータ型にも依存し、型のサイズに応じて掛け合わせて求められます。

時間計算量(Time Complexity)

アルゴリズムの時間計算量とは、そのアルゴリズムが完了までの実行に要する時間の量を表すものです。時間要件は数値関数 t(N) として表現でき、各ステップが一定の時間で実行されると仮定すれば、t(N) は「ステップ数」として測定できます。

たとえば、2つの n ビット整数の加算を考えると、N ステップが必要になります。したがって、総計算時間は t(N) = c × n と表せます。ここで c は、2ビットの加算に要する時間です。このことから、t(N) は入力サイズの増加に伴って線形に増加することが分かります。