オーダー記法 Part1 計算量の種類

f:id:shogonir:20200828030204p:plain

概要

ここでのオーダー記法は、アルゴリズムの性能(計算量)を評価するために使うものとします。
特に、あるアルゴリズムで問題を解く(計算する)際にかかる時間などの性能を表現できます。

ここからは、次のキーワードがでてきます。
もしまだご存知ないという方は、以前の記事を参照ください。

  • リスト探索
  • 線形探索
  • 二分探索

オーダー記法を学ぶとどのようなメリットがあるのでしょうか。
アルゴリズムの性能を評価できると、次のような問いに答えることができます。

  • 問1. 整列済みのリストを探索する場合、次の1と2のどちらが速いか?

    1. 線形探索
    2. 二分探索
  • 問2. 整列されていないリストを探索する場合、次の1と2のどちらが速いか?

    1. 線形探索を使う
    2. 整列してから二分探索を使う

上記の問1の答えは2で、問2の答えは1なのですが、
このシリーズを読んでいただくと、理解できるようになっているはずです。

ちなみに、この記事の内容はそのまま動画になっていますので、
そちらも興味があればご覧になってください。

youtu.be

オーダー記法シリーズの目次

  • 計算量の種類
  • オーダー記法
  • 定数時間と、計算量の性質
  • 計算量の導出
    • 線形探索
    • 二分探索
  • 計算量の演算

この記事では、「計算量の種類」について解説いたします。

計算量の種類

計算量とは、計算する(問題を解く)際に必要な量のことです。
よく使う計算量は時間計算量と空間計算量です。

計算量
+-- 時間計算量
+-- 空間計算量

時間計算量は問題を解く際にかかる時間のことです。
この量が小さければ小さいほど、速く問題を解けるので優れていると言えます。

空間計算量は問題を解く際に使用する空間のことです。
空間とは、ここではコンピュータ上のメモリなどの領域を指します。
この量が小さいほど、限られたリソースで動作するので優れています。

時間と空間のどちらが重要な指標であるかは状況によります。
たとえば、スパコンを使ってとにかく速く問題を解きたい時は、
時間計算量を重視して空間計算量は少しぐらい大きくなってもいいでしょう。
逆に組み込み系の限られたリソースしかないときは、
空間計算量を重視せざるを得ないということになります。

状況によるとはいえ、一般的なケースについても言及したいと思います。
ただ、時間がかかることのストレスは人間が感じやすいので、
一般的には時間の方を重視すると思っていいと思います。
とはいえ、空間計算量が現実的である必要はもちろんあります。

というわけで、ここまでで二つの計算量について紹介しました。
しかし、これらの計算量はより細かく分類できるのです。

これらの計算量は、どのような状況を考えるかによっても変化します。
例えば、 最悪 , 平均 , 最良 などの状況があります。
最悪 はリスト探索の場合、最後まで要素が見つからないような状況で、 最良 はその逆です。
平均 は色々な入力に対しての計算量の平均です。

特に 最悪平均 の計算量は使う機会が多いです。
最良 についてはそこまで使う機会は少ないと思います。
最良 の場合について考えて「二分探索も線形探索も数ステップで問題を解く」ことが分かっても、
二つのアルゴリズムの性能を比較することができないからです。

さいごに

というわけで、この記事では計算量の種類について紹介しました。
この記事で紹介した計算量を表にまとめました。

計算量
 |
 +- 時間計算量
 |   +- 最悪時間計算量
 |   +- 平均時間計算量
 |   +- 最良時間計算量
 |   +- ...
 |
 +- 空間計算量
     +- 最悪時間計算量
     +- 平均時間計算量
     +- 最良時間計算量
     +- ...

次の記事では、計算量を数学的に記述する方法である 「オーダー記法」について紹介したいと思います。

オーダー記法をマスターすれば、アルゴリズムの性能という
一見すると評価しにくい指標を客観的に評価できるようになります。
また、同じ問題を解くにしても、アルゴリズムを工夫するだけで その実行速度が何万分の一になったりすることもあります。

同じ結果を出すのに、桁違いのスピードを出すことができる アルゴリズムの世界についてシリーズで紹介していきたいと思います。

次のオーダー記法の記事についても是非読んでいただきたいです。