「大人の教養・知識・気付き」を伸ばすブログ

一流の大人(ビジネスマン、政治家、リーダー…)として知っておきたい、教養・社会動向を意外なところから取り上げ学ぶことで“気付く力”を伸ばすブログです。目下、データ分析・語学に力点を置いています。

MENU

Pythonで学ぶアルゴリズム(05/18)

 アルゴリズムを学ぶのにPythonの学習も兼ねて

を参照していく。

4. ソートを改良する

4.1 問題を分割する

 アルゴリズムにおいても問題を分割することは有用である。

4.1.1 小さなソート

 多くの数をソートすることを考えるとき、そうではなく、既にソートされた配列(複数の列)を1つの数値と見なし、更にそれらをまとめた新たな配列と見なして更にソートすることを繰り返していくことを考える。すなわち

問題
 2つのソートされた配列をまとめて1つのソートされた配列を作る手順を考える。

 この作業をマージと呼ぶことにする。

4.1.2 ソートされた配列のマージ

 参照している配列の要素を示すものとしてポインタを考える。このソート問題では、ポインタがある場所の数値を比較するだけでよい点が望ましい。

4.1.3 マージの計算量

 マージの計算量を考える。数の比較を行う回数は、比較する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}

を得る。したがって最右辺の最も次数の高いn\log_2 nを取ることで\mathcal{O}(n\log_2n)を得る。

4.1.5 分割統治法

 マージソートの本質は問題を小さく分割し簡単な問題を解くことを重ねて全体の解を得る点にある。このような方法を一般に分割統治法という。

プライバシーポリシー お問い合わせ