TechFULの中の人

triple-four’s blog

初心者でも理解できるアルゴリズムの実行時間評価方法

こんにちは!TechFULのメンバーのチャンニャットタムです。

皆さんがTechFulのチャレンジ問題やハッカソンイベントの問題にチャレンジしたとき、解法が正しいと思っているのにテストケースの一部が通らないということがありませんか。

もちろんコードのミスもありますが、一番多くあるパターンは問題の制限時間に間に合っていないことです。制限時間に間に合わせるためには、自分の解法にどれだけの時間がかかるか知ることが重要です。
それでは、自分の書いたコードにかかる時間を簡単に評価する方法を紹介したいと思います。

アルゴリズムの効率

上記のように問題を解くためのアルゴリズムを考えるとき、アルゴリズムの効率を評価する必要があります。 アルゴリズムを評価するときは以下の二つを主に評価します。

  • 時間計算量:プログラムを実行するために必要な時間を意味します。
  • 領域計算量:プログラムを実行するために必要な記領域を意味します。

今回は初心者向けのため時間計算量(time complexity)について話させていただきます。

O表記法

一般的に使われているのは(オー記法またはビッグオー記法)O( f(n) ) ( n は入力サイズ)です。
ここでf(n)とは入力サイズとしたnの変化を表す関数です。
O( f(n) ) と表記すると時間計算量がf(n)に比例することを意味します。
アルゴリズムを評価するときは、入力サイズの上限を考えて評価します。

計算量を求めるルール

係数省略ルール

アルゴリズムAの実行時間は T(n) = O( k * f(n) ) kは係数である場合: T(n) = O( f(n) ) と言えます。なぜk を省略できるのでしょうか?
アルゴリズムの計算量を求めるとき、最悪の場合を考えて評価するため、n が大きくなるほどk の影響が小さくなります。そのため、k を考える必要がありません。

最大値選択ルール

アルゴリズムAの実行時間が T(n) = O( f(n) + g(n) ) の場合:
T(n) = O( Max( f(n) , g(n) ) と言えます。
例えば T(n) = O( n ^ 2 + n + 3 ) の場合は T(n) = O( n ^ 2 ) となります。

加算ルール

アルゴリズムAは二つの部分から構成されるとします。
部分1の実行時間は :T_{1}n = O( f(n) )
部分2の実行時間は:T_{2}n = O( g(n) )
アルゴリズムA全体の計算量は T(n) = T_{1}n + T_{2}n = O ( f(n) + g(n) )  であり、
さらに、最大値選択ルールを利用すると、T(n) = O ( Max( f(n) , g(n) ) ) となります。

乗算ルール

プログラムAの実行時間がT_{1}(n) = O( f(n) であるとします。
プログラムAをk(n) = O( g(n)  回実行させると全体の時間計算量がO( f(n) \times g(n) ) となります。

例から理解しましょう!

以下の例では、C#を使用しています。

例1

for( int i = 0 ; i < N ; i++ ){
    x += a[i] ;
}
for( int i = 0 ; i < N ; i++ ){
    x += a[i] ;
}
for( int i = 0 ; i < N ; i++ ){
    x += a[i] ;
}

ソースコードを見ると、ループの時間計算量はO(N) で、ループが連続3回でます。
そのためこのプログラムの時間計算量は O( N + N + N ) 、係数省略ルールまたは最大値選択ルールを利用して O(N) となります

例2

次は小さい順にソートするバブルソートの計算量を評価してみます。

for( int i = 0 ; i < N ; i++ ) (1)
    for( int j = i+1 ; j < N ; j++ ) (2)
        if( a[i] < a[j] ){ (3)
            int swap = a[i];
            int a[i] = a[j];
            int a[j] = swap;
        }

ソースコードを見るとループ(1)がN回実行されます。
ループ(1)の1回目でループ(2)がN-1回実行されます。
ループ(1)の2回目でループ(2)がN-2回実行されます。
ループ(1)の3回目でループ(2)がN-3回実行されます。
・・・
ループ(1)のN回目でループ(2)が1回実行されます。

最悪の場合、処理(3)1 + 2 + ... + N - 1 =  \frac{n( n -1 )}{2} 回実行されるため、 時間計算量は O( \frac{n ( n - 1 ) }{ 2} ) = O ( n ^ 2 ) となります。

パソコンの処理能力と問題の制約

パソコンの種類により処理能力が多少異なりますが、一般的には1秒で10 ^ 8回計算ができます。 アルゴリズムの実行時間を評価するときは、これを基準に評価しましょう!

よく利用される時間計算量の関数を確認しましょう

n logn \sqrt{n} nlogn n ^ 2 2 ^ n n!
5 2 2 10 25 32 120
10 3 3 30 100 1024 3628800
20 4 4 80 400 1048576 約2.4 x 1018
50 5 7 250 2500 約1015 約3.0 x 1064

運営会社 / サービス

444株式会社

triple-four.com

TechFUL

procon.techful.jp