1.2   アルゴリズムとは何か

1.2.1   アルゴリズムの定義

アルゴリズムは、有限時間内で特定の問題を解決するための一連の指示またはステップです。以下の特徴があります：

• 問題が明確に定義されており、入力と出力の明確な定義が含まれています。
• アルゴリズムは実行可能で、有限の回数のステップ、時間、メモリ空間内で完了できることを意味します。
• 各ステップには明確な意味があります。同じ入力と条件の下で出力は一貫して同じです。

1.2.2   データ構造の定義

データ構造は、コンピュータ内でデータを組織し保存する方法で、以下の設計目標があります：

• コンピュータのメモリを節約するために空間占有を最小化する。
• データ操作を可能な限り高速にし、データのアクセス、追加、削除、更新などをカバーする。
• 効率的なアルゴリズム実行を可能にするために、簡潔なデータ表現と論理情報を提供する。

データ構造の設計はバランスを取る行為であり、しばしばトレードオフが必要です。一つの側面を改善したい場合、しばしば別の側面で妥協する必要があります。以下は2つの例です：

• 配列と比較して、連結リストはデータの追加と削除においてより便利ですが、データアクセス速度を犠牲にします。
• 連結リストと比較して、グラフはより豊富な論理情報を提供しますが、より多くのメモリ空間が必要です。

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

以下の図に示すように、データ構造とアルゴリズムは高度に関連し、密接に統合されており、具体的には以下の3つの側面があります：

• データ構造はアルゴリズムの基礎です。構造化されたデータ保存とアルゴリズムのためのデータ操作方法を提供します。
• アルゴリズムはデータ構造に活力を注入します。データ構造だけではデータ情報を保存するだけです。アルゴリズムの応用によって、特定の問題を解決できます。
• アルゴリズムは異なるデータ構造に基づいて実装できることが多いですが、実行効率は大きく異なることがあります。適切なデータ構造を選択することが鍵です。

図 1-4   データ構造とアルゴリズムの関係

データ構造とアルゴリズムは、以下の図に示すように、ブロックのセットに例えることができます。ブロックセットには多数のピースが含まれ、詳細な組み立て説明書が付いています。これらの説明書に段階的に従うことで、複雑なブロックモデルを構築できます。

図 1-5   ブロックの組み立て

両者の詳細な対応関係は以下の表に示されています。

表 1-1   データ構造とアルゴリズムをブロックと比較

データ構造とアルゴリズム	ブロック
入力データ	未組み立てのブロック
データ構造	ブロックの組織、形状、サイズ、接続などを含む
アルゴリズム	ブロックを望ましい形状に組み立てる一連のステップ
出力データ	完成したブロックモデル

データ構造とアルゴリズムはプログラミング言語から独立していることは注目に値します。この理由により、この本は複数のプログラミング言語での実装を提供できます。

慣習的な略語

実生活の議論では、「データ構造とアルゴリズム」を単純に「アルゴリズム」と呼ぶことがよくあります。例えば、よく知られたLeetCodeアルゴリズム問題は、実際にはデータ構造とアルゴリズムの両方の知識をテストしています。