Pythonで学ぶアルゴリズム（05/18） - 「大人の教養・知識・気付き」を伸ばすブログ

　マージの計算量を考える。数の比較を行う回数は、比較する2つの配列の長さをそれぞれ $a,b$ とすれば、各ステップでそれぞれのポインタを指す要素が比較されることから、 $a+b-1=n-1$ であり、すなわち $\mathcal{O}(n)$ である。これが2つのソート済みの配列を基に1つのソートされた配列を作るのにかかる計算量である。

def merge_arrays(left, right = []):
    res = []
    i, j = 0,0
    n, m = len(left), len(right)
    
    # 一方の配列を調べ尽くしたら終了とする
    while i < n and j < m:
        if left[i] < right[j]:
            res.append(left[i])
            i +=1
        else:
            res.append(right[j])
            j += 1
    # 残りはそのまま後ろに連結する
    return res + left[i:] + right[j:]

def step(array):
    res = []
    for i in range(0, len(array), 2):
        res.append(merge_arrays(*array[i:i+2]))
    return res

# 実際にテストデータを使って動かしてみる
import random

random.seed(4)
my_array =[random.randint(1,100) for i in range(150)]
my_array = [[v] for v in my_array]
step1 = step(my_array)
print(step1)

print('###################')
step2 = step(step1)
print(step2)

print('###################')
step3 = step(step2)
print(step3)

print('###################')
step4 = step(step3)
print(step4)

print('###################')
step5 = step(step4)
print(step5)

print('###################')
step6 = step(step5)
print(step6)

print('###################')
step7 = step(step6)
print(step7)

print('###################')
step8 = step(step7)
print(step8)

4.1.4　マージソートの計算量

　マージソートは、二分木と呼ばれるイメージでマージする過程を図示できる。

二分木のイメージ

　ソートする入力配列のサイズを $n$ とする。 $1$ ステップの計算では2つの配列をマージする計算だとする。高さが $n\leq2^k$ を満たすような最小の $k\in\mathbb{N}$ となるような木を用意する。このとき

$\begin{aligned} k=\log_2 n \end{aligned}$

である。木の高さを1つ減らすために必要なマージの回数は葉の枚数の半分であり、これは高々 $n$ 回である。したがって

$\begin{aligned} \mathcal{O}(nk)=\mathcal{O}(n\log_2 n) \end{aligned}$

がマージソートの計算量である。

4.1.5　ソートの計算量

　マージソートの計算量 $\mathcal{O}(n\log_2 n)$ よりも少ない計算量のソートアルゴリズムは存在しない。
　長さ $n$ の配列 $[a_1,\cdots a_n]$ を考える。 $i\lt j$ を満たすような添え字に対して $a_i\gt a_j$ ならば2つの要素を入れ替え、小さな要素が先頭により近くなるようにする。一方で長さ $n$ の配列の要素がすべて違うならば、この $n$ 個の要素を用いて表現できる配列の種類は $n!$ 通り存在する。これは $n$ 種類の要素を1列に並べる順列の数である。1回の比較演算では比較した要素を入れ替えるか、そのままにするかの二択が存在する。このときの二分木における高さがソートアルゴリズムに最低限掛かる計算量である。
　木の高さを $k$ とすると、葉の枚数は $2^k$ である。アルゴリズムはすべての可能性を実現できなければならないから、

$\begin{aligned} 2^k\geq n! \end{aligned}$

でなければならない。
　Sterlingの公式より

$\begin{aligned} n!\approx\sqrt{2\pi n}\left(\displaystyle{\frac{n}{e}}\right)^n \end{aligned}$

と近似できるから、

$\begin{aligned} &2^k\geq n!\approx\sqrt{2\pi n}\left(\displaystyle{\frac{n}{e}}\right)^n\\ \Leftrightarrow\ &k=\log_2\left\{\sqrt{2\pi n}\left(\displaystyle{\frac{n}{e}}\right)^n\right\}\\ \Leftrightarrow\ &k=n\log_2{\sqrt{2\pi n}}+n\log_2 n-n\log_2e \end{aligned}$