計算量

アルゴリズムを実行するにあたって計算機が必要とするリソース(資源)の大きさのこと。

時間計算量と記憶計算量の2種類がある。また、それぞれに最もリソースを利用してしまう場合の計算量である最悪計算量と、平均計算量の2つの評価方法がある。一般に、最悪計算量に注目してアルゴリズムが考えられる。

小規模なデータを扱うならばアルゴリズムの計算量が問題になることは少ないが、データ量が多くなるとアルゴリズムの質によって計算量が天文学的数字になってしまい、計算が終了するのに1000年近くかかってしまったり、メモリーがいくらあっても足りないという事態が発生する。そのためアルゴリズムを作るにあたっては、データ量に対しての計算量の増加傾向をしっかり把握することが必要になってくる。

ソートアルゴリズムのように最悪計算量がO(n log n)であると証明されているものも存在する。しかし、そのような例は稀である。

通信用語の基礎知識検索システム WDIC Explorer Version 7.04a (27-May-2022)