2章 アルゴリズムと計算量

計算量の評価

時間計算量：プログラムの実行に必要な時間を評価します。計算機の プロセッサをどれだけ利用するかを見積もります。 領域計算量：プログラムの実行に必要な記憶領域を評価します。計算機のメモリをどれだけ利用するかを見積もります。

一般的にはシステムの環境を考慮したうえで、時間計算量と領域計算量のトレードオフやバランスを考えてアルゴリズムを設計する。（例えば、メモリを多く使う（領域計算量が増加）ことで、計算時間を短縮することができる）

O表記法

アルゴリズムの効率を評価するものさしのひとつ Big-Oh-Notationとも呼ばれ、例えばO(n)やO(n^2)のようにnを問題の入力サイズとした関数でアルゴリズムの効率を表す。 アルゴリズムの計算量は最善・平均・最悪の場合について見積もることができるが、最悪の計算量をもとに考えることがおおい。

計算量の比較

• logn, √n, n, nlogn, n^2, 2^n, n!の順に計算量が大きくなる

3章 初等的整列

ソートアルゴリズムを選択する際の観点

• 計算量と安定性
• データを列を保持する1つの配列以外にメモリが必要にならないか
• 入力データの特徴が計算量に影響しないか

4章 データ構造

データ構造は以下の3つの概念から成り立っている

• データの集合：対象となるデータの本体で、例えば、配列や構造体などの基本データ構造 でデータの集合を保持します。

• 規則：データの集合を一定のルールに従って正しく操作・管理・保持するための決まり事で す。どういった順番でデータを取り出すかなどの取り決めです。

• 操作：「要素を挿入する」や「要素を取り出す」などの、データの集合に対する操作です。 「データの要素数を調べる」や「データの集合が空かどうか調べる」といった問い合わせも 含まれます。

• Stack: LIFO

• Queue: FIFO

• List: 双方向連結リスト