はじめに

今回は、アルゴリズムの計算量についてまとめていきたいと思います。

計算量とは

アルゴリズムの良し悪しを決める重要な指標
計算量が少ない方が、処理が早くなるということなので、アルゴリズムとしてはいいものとなる。

ランダウ記号

ランダウ記号とは、アルゴリズムAの計算時間T(N)が概ねP（N）に比例するということを、T(N) = O(P(N))であると表現し、アルゴリズムAの計算量はO(P(N))であるという。
例えば、一重のfor文の計算量はおおよそO(N)で、二重になると、O(N^2)です。
あるアルゴリズムの計算量が、3N^2+10N+100になったとすると、以下の手順でこのアルゴリズムの計算量をランダウ記号を用いて表す。
・最高次以外の項を無視→3N^2
・係数を無視→N^2
よって、O(N^2)

以下のような、あるNが与えられた時の偶数のみ出力するアルゴリズムの計算量を考えます。

for n in stride(from: 2, through: N, by: 2) {
    print(n)
}

for文の反復回数はN/2回なので、計算量は概ねNに比例していることから、O(N)です。

さらに、少し難しい例として、最近点対問題を考えてみます。

正の整数NとN個の座標点(Xi, Yi)(i = 0, 1, 2, ..., N-1)
が与えられているとき、最も距離が近い2点間の距離を求める

全ての点対に対して距離を計算してそのうちの最小のものを出力する方針です。

let N = 100
func calculateDistance(Xa: Double, Ya: Double,
                       Xb: Double, Yb: Double) -> Double {
    return sqrt((Xa - Xb) * (Xa - Xb) + (Ya - Yb) * (Ya - Yb))
}
var x = [Int]()
var y = [Int]()
for _ in 0..<N {
    x.append(Int.random(in: -N*N...N*N))
    y.append(Int.random(in: -N*N...N*N))
}
var minimumDistance = Double(Int.max)
for i in 0..<N {
    for j in i+1..<N {
        let distance = calculateDistance(Xa: Double(x[i]),
                                         Ya: Double(y[i]),
                                         Xb: Double(x[j]),
                                         Yb: Double(y[j]))
        if distance < minimumDistance {
            minimumDistance = distance
        }
    }
}
print(minimumDistance) // 例えば、108.15729286552988

解説
Nは本来であれば、もっと大きい値として定義したいのですが、Swiftのコンパイルが遅くて、今回は100としておきました。
calculateDistanceは2点間の距離を求める関数です。
配列x, yにN個のランダムな要素を格納します。
minimumDistanceは、十分大きな値で初期化しておきます。
一つ目のfor文は、１個目の点をN通りに試す処理をしています。（添字i）
二つ目のfor文は2個目の点を順に試す処理をしています。（添字j）
注意点として、添字jが動く範囲は0からN-1ではなく、i+1からN-１で十分だということです。例えば、以下のような点同士の距離は明らかに等しく、計算するだけ無駄です。
i=2, j=5の場合: (X2, Y2)と(X5, Y5)との距離
i=5, j=2の場合: (X5, Y5)と(X2, Y2)との距離
また、iとjが同じ点は異なる2点でなく、同じ点を示すので、jはi+1からスタートさせます。

i=0の時j=1, 2, ..., N-1のN-1回
i=1の時j=2, ..., N-1のN-2回
i=2の時j=3, 2, ..., N-1のN-3回
...
i=N-2の時j=N-2, N-1の2回
i=N-1の時j=N-1の1回

つまり、反復回数T(N)は、k=0からN-1までのΣ(N-1-k)となり、これを計算すると、(1/2)(N^2-N)となる。
よって、計算量はO(N^2)となります。
ちなみに、N個のものから異なる2点を選ぶので、込み合わせの総数はnC2=(1/2)(N^2-N)となります。

また、Nがいくつであってもその数によらないようなアルゴリズムの計算量はO(1)というふうに表現します。

問題

適当な問題を出すので、理解できているか不安な方はチャレンジしてみてください。

問題1: 以下の計算時間をランダウ記号Oを用いて示してください。

1.
T1(N) = 1000N
2.
T2(N) = 2N^2+2N-3
3.
T3(N) = 100N-11N^2-5NlogN
4.
T4(N) = 2^N+N^10000

問題2: 以下の計算量はいくらになるのか求めてください。

for i in 0..<N {
    for j in i+1..<N {
        for k in j+1..<N {

        }
    }
}

答え

O: ランダウ記号

問題1

1.
O(N)
2.
O(N^2)
3.
O(N^2)
4.
O(2^N)

問題2

0 <= i < j < k < N を満たす (i, j, k) の組の個数を数え上げればよいので、nC3 = (1/6)N(N-1)(N-2)となり、答えは
O(N^3)である。

おわりに

終わりです。

【algorithm】計算量とランダウ記号

はじめに

計算量とは

ランダウ記号

問題

答え

おわりに