アルゴリズムにおけるTime Complexity (時間計算量)について

こんにちは、BaseconnectのエンジニアのEndratno Alvinです！ 本日は、アルゴリズムの性能を評価するための概念を紹介したいと思います。

Time Complexity (時間計算量) とは？なぜ必要なのか？

あるアルゴリズムの速度を特定するために、実行時間を測定することはほとんどの状況において適切な方法とはなりません。なぜなら、測定結果はCPUの速度、データ量などの外的要因の影響を受けるからです。そのため、私たちには外的要因に依存せず、アルゴリズムの速度を評価する方法が必要になります。それがTime Complexity (時間計算量)です。Time Complexityは、多くの場合 Big O Notation(ビッグ オー記法)で表すことができます。

Big O Notion

概念

Big Oは、アルゴリズムが小さいサイズの入力でどれだけうまく機能するかを評価しません。 大きなデータを入れた場合に実行速度がどうなるかによって、時間計算量が変わります。

多くの場合、Big O表記法は、アルゴリズムの最悪のシナリオを表現します。 つまり、実行数（ループ数など）が一番多くの場合を考えて、それの係る時間を表しています。

係数と定数

従って、Big Oで記述するときに、実行時間の係数と定数は考慮しません。例えば、一つのデータの処理時間は５秒であっても、１０秒であっても、実行時間のグラフで表す線の曲が同じである限り、時間計算量は同じです。

また、Big O を特定するために、処理を実行する前に必要な準備時間などの定数も考慮しません。なぜなら、データが大量になると全体の処理時間が長くなり、準備時間の影響が小さくなり誤差とみなせるようになるからです。

例で考える、実際に時間計算量を求めてみましょう

Linear Time Complexity (O(n))

箱を想像してみましょう。4つの箱があるとします。その4つの箱の１つに宝が入っています。他の箱には何も入っていないとします。

宝を探すには箱を開けて、確認して、宝を見つかるまで繰り返していきます。１箱を開ける必要な時間は２秒とすれば、4つの箱を開ける必要な時間は8秒です。40個の箱を開けるのに必要な時間は80秒です。箱の数が増えれば宝探しにかかる時間も増えます。

箱を開けるのに必要な時間　x　箱数

箱を開けるために必要な時間（処理時間）をOにして、箱の数（データ量）をｎとすれば、このアルゴリズムの時間計算量はO(n)で表すことができます。

Quadratic Time Complexity O(n2)

他の場面を考えてみましょう。 同じく箱があって、その箱の中に１箱に宝があるとします。しかし、今回は箱をあけるために鍵が必要になります。鍵は全箱分あります。一つの鍵で一つの箱を開けられるとは限りません。

最悪の場合、すべての箱を確認する必要があります。従って、一つの宝箱に対し、全部の鍵を試すを必要があります。鍵を試すのに２秒かかるとすれば、最悪の場合、４つの箱場合は４つの鍵　ｘ　４つの箱　ｘ　２秒の時間が必要です。まとめると下記になります。

箱を開ける必要な時間　ｘ　鍵の数（箱の数と同じ）　ｘ　箱の数

前と同じ方法で、Big O で表せば O(鍵数　ｘ　箱数）なので O(n2) になります。

Constant Time Complexity O(1)

時間計算量を求めるのに慣れていただけましたでしょうか。以下は時間計算量を最小にするベストなアルゴリズムのTime Complexityを紹介したいと思います。 上記と同じ場面ですが、今回は犬を使って、宝を特定することにしました。その犬は「宝を特定する」という特別な才能を持っていることとします。

どれだけ宝箱があっても、一発で特定できる犬がいるおかげで、すぐに宝が入った宝箱を見つけることができます。

この場合、データ数に関係なく、実行時間が同じになります。この場合はO(1)と表すことができます。

Exponential Time Complexity O(kn)

もう少し応用的な使い方も紹介します。 宝箱を開けるためにn桁の暗証番号を特定する必要がある場合の時間計算量はO(kn)となります。

kは桁の進数です。nは桁数です。10進数の８桁であれば、108通りを試す必要があります。この場合は O(kn)で表すことができます。

Cubic Time Complexity O(n3)

次に、宝箱の鍵に鍵が掛かっている場合を考えましょう。プログラミングの目線で言えばループの中にループがあるい場合となり、 O(n3)で表せます。

Linearithmic Time Complexity O(n log n)

上記のO(n2)と同じようなケースですが、今回は、一つの鍵で一つの箱しか開けられないことがわかったとします。 ある鍵で箱を開けた後、その鍵は他の箱を開けられることがないため、鍵を捨てることができます。箱を開けるたびに、試す鍵が少なくなります。 従って、箱を開けるためにかかる時間が箱を開けていく毎に減少していくことになります。

上記のTime Complexityは O(n log n)で表すことができます。O(n2)よりは早いですが、O(n)より遅くなります。

Logarithmic Time Complexity O(log n)

宝箱のうちに半分を一度で探すツールがある場合は時間計算量はO(log n)になります。

まとめ

Time Complexity の「悪い」から「良い」順に並べれば、以下の順になります：

  1. O(kn)
  2. O(n3)
  3. O(n2)
  4. O(n log n)
  5. O(n)
  6. O( log n)
  7. O(1)

おわりに

開発者はより良いプログラムは誰でも書きたいと思います。プログラムを書く際に、特別な才能を持つ犬や一度でに半分を探すツールを取り入れられるかどうか、使った鍵をまた試しているかどうか、最善の時間計算量を使うことを意識することはより良いプログラムを作ることにつながると考えています。

Baseconnectではエンジニアメンバーを絶賛募集中です。 もしご興味をお持ちいただけた方がいらっしゃいましたら、下記のリンクよりぜひカジュアルにお話しさせていただけましたら嬉しく思います！

herp.careers