1. REON

    Posted

    REON
Changes in title
+【algorithm】計算量とランダウ記号
Changes in tags
Changes in body
Source | HTML | Preview
@@ -0,0 +1,141 @@
+#はじめに
+今回は、アルゴリズムの計算量についてまとめていきたいと思います。
+
+#計算量とは
+アルゴリズムの良し悪しを決める重要な指標
+計算量が少ない方が、処理が早くなるということなので、アルゴリズムとしてはいいものとなる。
+
+
+#ランダウ記号
+ランダウ記号とは、アルゴリズム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が与えられた時の偶数のみ出力するアルゴリズムの計算量を考えます。
+
+```swift
+for n in stride(from: 2, through: N, by: 2) {
+ print(n)
+}
+```
+
+for文の反復回数はN/2回なので、計算量は概ねNに比例していることから、O(N)です。
+
+さらに、少し難しい例として、最近点対問題を考えてみます。
+
+```swift
+正の整数NとN個の座標点(Xi, Yi)(i = 0, 1, 2, ..., N-1)
+が与えられているとき、最も距離が近い2点間の距離を求める
+```
+
+全ての点対に対して距離を計算してそのうちの最小のものを出力する方針です。
+
+```swift
+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文は、1個目の点をN通りに試す処理をしています。(添字i)
+二つ目のfor文は2個目の点を順に試す処理をしています。(添字j)
+注意点として、添字jが動く範囲は0からN-1ではなく、i+1からN-1で十分だということです。例えば、以下のような点同士の距離は明らかに等しく、計算するだけ無駄です。
+i=2, j=5の場合: (X2, Y2)と(X5, Y5)との距離
+i=5, j=2の場合: (X5, Y5)と(X2, Y2)との距離
+また、iとjが同じ点は異なる2点でなく、同じ点を示すので、jはi+1からスタートさせます。
+
+```swift
+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を用いて示してください。
+
+```swift
+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: 以下の計算量はいくらになるのか求めてください。
+
+```swift
+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)である。
+
+#おわりに
+終わりです。