アルゴリズムという① 「処理手順」の良し悪しを知りたい。
・仮想的な計算モデルを使用→CPUやメモリの物理的な要素は考慮しない。1つの命令は1単位時間で実行されるものとする。
・命令の実行回数を指標にする…② 時間計算量
・使用するメモリ容量を指標にする…③ 空間計算量
解ける問題の規模を決めるのが②であったり、メモリは安かったりすることなどから、多くの場合、アルゴリズムの性能は②で表す。

②は、入力データサイズ(数や上限)をもとに算出する。

・④ 最大計算量
最悪の場合のデータを扱ったときの計算量。
最悪の場合を想定するのが無難なことから、多くの場合はこれを用いる。

・⑤ 平均計算量
すべての入力に対する計算量の平均。最悪のパターンがめったに起こらないときに用いる。

\(2^{x} = n\) である \(x\) は、
\(x = \log_{2}n\)と表す。

\(\log_{2}128\) = ⑥ 7

○オーダーの概念
計算量全体の傾向をとらえたもので、データ数nが十分大きいときを考える。
そのため、計算量全体の中で、影響の小さいものは無視できる。
和は大きい方のみを採用し、積は積を行う。
\(o(n^{2})+o(n) = o(n^{2})\)
\(o(n^{2})o(n^{3}) = o(n^{5})\)

オーダーのパターン(下に行くほど、低速)
\(O(1)\)
\(O(\log(n)\)
\(O(n)\)
\(O(n\log(\log(n)))\)
\(O(n\log(n))\)
\(O(n\sqrt{n})\)
\(O(n^{2})\)
\(O(n^{3})\)
\(O(2^{n})\)

必ずしも「簡潔」なアルゴリズム=「良い」アルゴリズムであるとは限らない、計算量の評価が必要。
・速くてメモリをあまり使わない→⑦ ◎
・遅くてメモリをたくさん使う→⑧ ×
・速いがメモリをたくさん使う→⑨ ？
・遅いがメモリをあまり使わない→⑩ ？

・時間計算量…主として⑪ アルゴリズム
・空間計算量…主として⑫ データ構造