データ構造
問題を効率的に解くに当たって、機械にどのような情報を持たせるか、によって計算量や時間は変わってくる。
例
よく見る例としては、配列・リストの違いが挙げられる。
配列・リストは、どちらもデータを順序立てて記録するときに使う。（この用語の使われ方はハッキリとした定義があるわけではなく、言語等によって変わるが、ひとまずは以下に示すものを指すということで）
配列
配列は、データ数分の領域をメモリ上に確保し、順番に格納する。
┌─┬─┬─┬─┬─┐
データ│ 3│ 1│ 4│ 1│ 5│
└─┴─┴─┴─┴─┘
メモリ [ 0][ 1][ 2][ 3][ 4]
リスト
リストは、データはメモリ上にはバラバラに存在し、値と次のメモリアドレスをセットで保持する。
値 次
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
データ│ 3│10│→│ 1│50│→│ 4│20│→ …
└─┴─┘ └─┴─┘ └─┴─┘
メモリ [ 0] [10] [50]
比較
| 配列 | リスト | |
|---|---|---|
| 必要メモリ領域 | 小 | 大 |
| ランダムアクセス | 速い | 順番に辿るため遅い |
| 要素の数 | 固定 | 増減可能 |
| 入れるデータの型 | 固定 | 自由 |
| 要素の途中への追加・途中からの削除 | 後ろを1つずつずらすため遅い | アドレスの書き換えのみで済むため速い |
など、両者にメリットデメリットがあることがわかる。
要素数が変わったり追加削除が頻繁に行われるならリスト、データが大量だったり速度が求められる場合には配列、など、適切なデータ構造を使い分けることがよりよいプログラムには重要となる。
