計算量 external_link

時間計算量 (time complexity)

アルゴリズムの実行で消費される時間量である。

実行時間はコンピュータの性能に依存するため普遍的な量として評価できない。
そこで、普遍的な量として評価できるよう特定操作を１単位とした操作回数を時間計算量とする。

時間計算量	表記例
最悪	$O(n),\ O(n^2)$
最良	$\Omega(n),\ \Omega(n^2)$
平均	$\Theta(n),\ \Theta(n^2)$

※ $n$：入力データの個数

領域計算量 (space complexity)

アルゴリズムの実行で使用する空間的領域の大きさである。

アルゴリズムが消費する記憶容量(ビット、バイト、ワード）もコンピュータの性能により異なるため普遍的ではない。
このためアルゴリズムで使われた変数の数などを領域計算量とする。

---

🌏 Map

same layer	lower layer