データ構造とアルゴリズムの計算量と実装

データ構造とアルゴリズムについて勉強したことを少しずつ書き足していきます。

計算量
O記法(ランダウの記号)
データ構造
データ構造ごとの各操作に必要な時間計算量
ソートアルゴリズム
参考

計算量

・計算量には時間計算量/空間計算量がある

・時間計算量は処理に必要な時間、空間計算量は処理に必要な記憶容量を指す

・時間計算量を考えるには実行時間ではなく命令数で考える(環境によって実行時間が変わる可能性があるため)

・時間計算量を考えることでデータのサイズや1回の処理時間がいくらかがわからなくても、アルゴリズムの性能が評価できるメリットがある

・時間計算量には最悪、最良、平均の計算量があり、最悪計算量を用いて考えることが多い

・1回の実際の処理時間を見ると、O記法での計算量が少なく性能が良いと思われても実際にはより時間がかかる可能性もある

O記法(ランダウの記号)

・上から順に早い

O(log logn)

O(logn)

・二分探索など

O(n^1/2)

O(n)

・配列の全要素に一回ずつアクセス

・線形探索など

O(nlogn)

・クイックソート

・マージソート

O(n^2)

・2重ループで配列の全要素に1回ずつアクセス

・単純ソート、バブルソート、挿入ソート、シェルソート

O(n^logn)

O(2^n)

O(n!)

・集合分割問題

データ構造

配列

・要素を連続的に並べたデータ構造

・添え字を使って任意の要素を参照できる

・効率的にメモリを使用できる(要素以外の情報がなく、各要素が隙間なく格納されている)

・要素の追加/削除は非効率

・探索効率は高くない。

多次元配列

・各要素が配列で構成される

・多次元配列の場合は添え字も2,3個と重なっていく→array[1][3][0]

・各要素はメモリに保存されており、メモリアドレスを参照して各要素の値を確認する。この時、各要素はメモリの中で連続的に保存(メモリアドレスが連続的に並ぶ)されている方がメモリアクセスの効率が良い(添字の右側が頻繁に変わる方が良い)。これは、キャッシュの空間的局所性の恩恵。

ジャグ配列

・多次元配列の内、各要素(配列)の要素数が異なるもの

・可変長のデータを管理する際に用いると、必要なメモリだけを確保するので空間的な効率が良い

連想配列・連想リスト・辞書・マップ・ハッシュ

・添字に整数以外の値を用いることができる配列

・配列がもつ要素が連続的に並ぶ性質はない

・要素そのもの以外の情報が必要になるため配列よりも多くのメモリを必要とする

ハッシュテーブル

・連想配列の1つ

・pythonで言えばdictionary

・キーと値が1組になっている

・キーから値を呼び出すためにハッシュ関数を使って重複のないものに変換する

連結リスト

・各要素はメモリ上で連続的に並んでおらず、飛び飛びの位置にある。これを連結することで連結リストとする

・一方向に連結されている単方向リストと、前後の要素に連結されている双方向リストがある

・リストに先頭と末尾があるものを線形リストと呼び、最初と最後の要素がつながっているリストを循環リストと呼ぶ

単方向線形リスト

・単方向線形リストでは実際の要素(値)と、次の要素の場所(メモリアドレス)を示すデータがある。

・実際の要素(値)はvalue,次の場所はnextと変数を付けることがある

・先頭の要素ではvalueにダミーの値を入れるなどしておく(空にしておくこともある？)

・末尾の要素ではnextを空にしておくことで末尾であることを示す。

・末尾の要素の場所を別の場所に記憶しておくことで、効率よく新しい要素を追加することができる

※先頭から順にたどって末尾の要素を探すとO(n)の時間計算量となる

・要素の探索は非効率※先頭から順に探索するしかないため

・要素とその場所を示すデータが必要なため配列と比べるとメモリの使用は非効率

単方向循環リスト

・単方向線形リストとの違いは末尾のnextが先頭の要素を指していること

・先頭の要素のメモリアドレスと一致したときに終端判定を行うことができる

・新しい要素を末尾に追加するときは、その要素のnextは先頭要素になる

双方向線形リスト

・各要素は次の要素だけでなく、1つ前の要素が保存されているメモリアドレスの情報も持つ

・上記はprevとして表すことがある

・先頭の要素のprevはNullとしておく

・要素の追加や削除を行う時、1つ前のnextと次の要素のprevを変える必要がある

・単方向リストと比べて、各要素が保持する情報が増えるため、メモリをより多く消費する

双方向循環リスト

・双方向線形リストとの違いとして、最後の要素のnextが先頭の要素が保存される場所を示す。

・先頭の要素のprevは最後の要素の場所を指す

・循環リストはリスト内の途中から探索を開始することが多い場合には有利に働くとのこと

※具体的な例を調べる

スタック

・一番最後に格納したデータを最初に取り出すことができる

・下から上に向かって積み上げるようなイメージ

・ブラウザのWebページを戻る時などがイメージしやすい

・スタックへデータを載せることをプッシュ、取り出すことをポップと呼ぶ

・スタックから空かどうかを判定する機能も必要な場合が多い

・抽象データ型として扱える。→スタックが提供すべき機能(プッシュ、ポップなど)があれば、中身のデータ構造は配列、連結リスト、それ以外のデータ構造を使っても良い

・配列でスタックを管理する場合で、なおかつ配列の長さを変えることができない言語の場合は、スタック作成時に確保するメモリの領域を意識する必要がある。ただし、連結リストでは動的なメモリ確保ができる。

※Pythonであればあまり意識しなくても良さそうな気はする

・深さ優先探索を実装するときなどによく見る。※再帰的な処理と相性が良い？

・スタックの特性上、末尾の操作しか行わないため、途中の要素の削除や追加は考えない

・Pythonでの実装(リストを使用)

class Stack():
    def __init__(self):
        self.stack = []
    def push(self, item):
        self.stack.append(item)
        return self.stack
    def pop(self):
        item = self.stack.pop()
        return item
    def get_stack(self):
        return self.stack

test_stack = Stack()
test_stack.push(100)
#[100]
test_stack.push(200)
#[100,200]
test_stack.get_stack()
#[100,200]
test_stack.pop()
#200

class Stack():

def __init__(self):

self.stack = []

def push(self, item):

self.stack.append(item)

return self.stack

def pop(self):

item = self.stack.pop()

return item

def get_stack(self):

return self.stack

test_stack = Stack()

test_stack.push(100)

#[100]

test_stack.push(200)

#[100,200]

test_stack.get_stack()

#[100,200]

test_stack.pop()

#200

キュー

・スタックと同様抽象データ型として扱えるので、実際のデータ構造は配列や連結リストなどを使うことができる

・キューは最初に入れた要素から取り出すことができる。(先入れ先出し)

・キューに要素を追加することをエンキュー、キューから要素を取り出すことをデキューと呼ぶ

・Pythonでの実装(リストを使用)

class Queue():
    def __init__(self):
        self.queue = []
    def enqueue(self,item):
        self.queue.append(item)
        return self.queue
    def dequeue(self):
        item = self.queue[0]
        del self.queue[0]
        return item
    def get_queue(self):
        return self.queue

test_queue = Queue()        
test_queue.enqueue(100)
#[100]
test_queue.enqueue(200)
#[100,200]
test_queue.dequeue()
#100
test_queue.get_queue()
#[200]

class Queue():

def __init__(self):

self.queue = []

def enqueue(self,item):

self.queue.append(item)

return self.queue

def dequeue(self):

item = self.queue[0]

del self.queue[0]

return item

def get_queue(self):

return self.queue

test_queue = Queue()

test_queue.enqueue(100)

#[100]

test_queue.enqueue(200)

#[100,200]

test_queue.dequeue()

#100

test_queue.get_queue()

#[200]

配列での実装

・配列で確保したメモリが可変でない場合は末尾であることを示すtailと先頭であることを示すfrontが必要。

→エンキューの際、tailが指している場所に新しい要素を追加してtailを次の要素にずらす。

→デキューの際、先頭の要素を取り出した後でfrontの位置を次の要素にずらす。

→配列の長さは固定なのにエンキュー/デキューによりfrontとtailが右にずれた場合、いずれ配列の終端に到達する。その場合はtail、frontは先頭の要素に戻る(リングバッファ)。

※配列の長さが可変の場合はfront/tailは不要？

・キューが空であることの判定はfront == tailであるかを調べる

・キューが確保したメモリを全て使っているか(満杯)を調べる必要がある

連結リストでの実装

・先頭と末尾を指すポインタを持つ必要がある

・キューが空であることの判定はfrontがNULLであるかを調べる

・配列では先にメモリを確保しているので、存在していない要素をtailで指すことができるが、連結リストでは動的にメモリを確保するので存在していない要素をtailで指すことができない

木構造

・ノードと各ノードをつなぐ枝によって構成される

・あるノードから見て、下にあるノードは子、上にあるノードは親と呼ばれる

・一番上のノードを根(ルート)、一番下のノードを葉と呼ぶ

・各ノードが2つ以下の子を持つ木を二分木と呼ぶ

二分木

・葉以外の全ノードが2つ以下の子を持つ木構造。必ず2つの子を持つなら全二分木、全ての葉が同じ深さの場合は完全二分木と呼ぶ

・二分木の一部分を囲っても二分木になる(再帰的な構造)→部分木と呼ぶ

・二分木に含まれるすべてのノードを漏れなく被りなく調べることを走査(トラバース)と呼ぶ

・走査の方法は幅優先探索と深さ優先探索がある。

・深さ優先探索は根からスタートして葉にたどり着くまでたどっていく。行きがけ、通りがけ、帰りがけ順の3種類の探索方法がある

・幅優先探索は、根からスタートして次の階層を全て調べつくしてからさらに次の階層へ探索する

・メモリ管理をプログラマが行う言語では、メモリ解法時は子から先に行う。※親から解放を行うと、子へのアクセスが不正になるため。帰りがけ順探索に処理を行う。

※親から解放してしまったときにどうなるのかを調べる

・追加や削除などの操作を効率よく行うためには平衡木(高さが同じ)を維持する必要がある

・二分探索木は　左の子の値＜親の値＜右の子の値となるよう整頓した構造

※二分探索の実装

平衡木

・根から葉までの深さがなるべく均等になっている木

・片方の子ノードに連なっているよりも左右均等にわかれていた方が探索効率が良い

・追加、削除の処理を行う際に整理して構築していく

ヒープ

・格納されている要素から最大値、最小値を探すことに適した木構造

・3つ以上の子を持つこともできる

・根が最大値/最小値となるように作る。

・ヒープソートや優先度付きキューの実現に使われる

AVL木

・

赤黒木

・各ノードを赤か黒で色分けする二分木

・根ノードは黒とする

・赤ノードの子は黒ノードとする(赤は親子で連続してはならない)

・挿入時は必ず赤とする

・どの葉から見ても黒の数は同じ

・2-3-4木を二分木で表現した構造

・木のバランスはいびつになり得る

・挿入、削除、検索がO(log(n))で実行できる

・更新や削除が少なく検索が多い場合は赤黒木よりもAVL木の方が良い(赤黒木は歪な形になり得るため)

・更新や削除が多い場合はAVL木よりも赤黒木の方が良い

・AVL木は木の高さの保持が必要だが、赤黒木は各ノードの赤黒を1bitで管理するだけなのでメモリ効率が良い

優先度付きキュー

・各要素に優先度を持たせて、優先度が高いものから取り出せるようにした抽象データ型

・抽象データ型なので実装時はヒープ、二分探索木、連結リスト、配列など選択肢がある。ただし実装によって操作時の計算量が変化する

・値自体を優先度として考えることや、値とは別に優先度をつけることができる

・要素の取得は、格納時に優先度順に入れること、取り出し時に優先度の高いものを探す2種類がある

両端キュー

・要素の追加/削除をキューの先頭と末尾の両方で行うことができる。doube ended queueと書き、dequeと呼ぶ。

・スタックとキューの両方の性質を持つ。※pythonのdequeも両端キューで作られている？

動的配列による実装

・循環リストによる実装と比べて途中の要素への直接アクセス(ランダムアクセス)が効率的にできる

・中央から前方と後方に向かって要素を追加し、どちらかが端に達したらより大きな動的配列を作って移動させる手法がある

リングバッファによる実装

・リングバッファの一方の端に要素を追加するときに、他方の端に行き着いた場合は新たなリングバッファを作成して要素を移動させる

データ構造ごとの各操作に必要な時間計算量

配列

要素へのアクセス：O(1)

要素の追加：O(1)

要素の削除：O(n)

要素の探索：O(n)

連結リスト

先頭への要素の追加：O(1)

末尾への要素の追加：O(1)

要素の探索：O(n)

スタック

・末尾の要素の追加/削除：O(1)

キュー

木

完全二分木

・要素の追加：O(logn)

・要素の削除：O(logn)

・要素の探索：O(logn)

ヒープ

・根(最大値/最小値)の参照：O(1)

・要素の追加：O(logn)

・要素の削除：O(logn)

・要素の探索：O(logn)

優先度付きキュー

配列(非ソート)

・要素の参照：O(n)

・要素の追加：O(1)

・要素の削除：O(n)

配列(ソート済)

・要素の参照：O(1)

・要素の追加：O(n)　※追加時にソートが必要なため

・要素の削除：O(1)

二分探索木

・要素の参照：O(logn)

・要素の追加：O(logn)

・要素の削除：O(logn)

ヒープ

・要素の参照：O(1)

・要素の追加：O(logn)

・要素の削除：O(logn)

ソートアルゴリズム

・配列などのデータの集まりを昇順や降順に並べ替えるための手順

・安定でないソート：同じ値が複数ある場合で、ソート前とソート後で同じ値同士の位置関係が変化する可能性があること

・安定なソート：同じ値が複数ある場合でも、ソート前後で同じ値同士の相対的な位置関係が変化しないこと

※安定なソートが必要な場面について調べる

・対象のデータ列の中だけでソートできるものを内部ソート、新たに作業領域を確保する必要があるものを外部ソートと呼ぶ

単純ソート

・先頭の要素の値とそれより後ろの各要素の値を1つずつ比較し、順序関係が望む結果の逆であれば位置を交換する

・先頭の要素が終われば、2つ目の要素とそれ以降の各要素の値を1つずつ比較し、順序関係が望む結果の逆であればその位置を交換する。以降全ての要素で繰り返す

・安定でないソート

・計算量はO(n^2)　※各要素をそれ以降の要素と比較するため、実装が二重ループになる

選択ソート

・データの中で最大値/最小値を探し、そのデータと先頭のデータを交換する

・次に2番目の最大値/最小値を探し、そのデータと先頭から2番目のデータを交換する。

・以降繰り返す

・安定でないソート

・計算量はO(n^2)、ただし単純ソートと比べて最大値/最小値を確定させてから交換するため、交換回数を減らすことができる。

バブルソート

・データの先頭から順に、隣接する2つの要素を比較して大小関係が逆であれば交換することを末尾まで行う

・末尾までソートが終わったら、再度先頭に戻って同じ操作を末尾まで行う

・以降、大小関係が正しい状態になるまで繰り返す

・1周につき、要素数-1回の比較を行う。

・安定なソート

・計算量はO(n^2)

挿入ソート

・配列の前の方で部分的にソート済みの箇所を作り、ソートされていない要素をソート済みの要素群の適切な場所に挿入する

・配列で実装した場合、挿入を行うとそれ以降の要素を全て1つずつ後ろにずらす必要があるため、その分の時間計算量が必要となる

・ただし、これからソートする要素がソート済みの要素の中で末尾に入れるべき値だった場合、挿入にかかる計算量はO(1)となる。ソート済の要素が多いほど処理が速い

・配列の先頭に近くあるべき要素を先にソートすることができれば、効率よくソートできる

・時間計算量ではバブルソートなどと同じくO(n^2)だが、比較回数は少なくなるためバブルソートと比べて高速

・連結リストで実装した場合、挿入にかかる時間計算量は配列で実装したときよりも小さいため高速に処理できる。

・ソート済みの部分のどこに挿入する課は二分探索を用いることでさらに高速化できる。

・安定なソート

・時間計算量はO(n^2)

シェルソート

・ある間隔を決め、その間隔おきに挿入ソートを行う。

→[3,6,1,9,2,4,8,5,7]であれば、間隔を3とすると以下の組で挿入ソートを行う。

→[3,9,8]、[6,2,5]、[1,4,7]の3組でそれぞれ挿入ソートを行う

→[3,8,9]、[2,5,6]、[1,4,7]であり、全体では[3,2,1,8,5,4,9,6,7]となる。

・2回目は間隔を狭めて再度挿入ソートを行う

→[3,2,1,8,5,4,9,6,7]に対して、間隔を2とすると以下の組で挿入ソートを行う。

→[3,1,5,9,7]、[2,8,4,6]の2組でそれぞれ挿入ソートを行う。

→[1,3,5,7,9]、[2,4,6,8]であり、全体では[1,2,3,4,5,6,7,8,9]となる。

・配列の要素数に対する間隔の大きさと、間隔の狭め方が大切であり、ある間隔hを3倍して1を加えたものを次の間隔とするような形(実際には逆順)が良く使われる

・挿入ソートでは、配列の末尾にあるデータを挿入するときはO(1)の計算量で済むなど、ソート済みのデータが多いと効率的になる性質があったが、ある間隔ごとにソートを行うことで手前にあるべき要素を早い段階で手前に持っていくことで挿入時の1つずつずらす操作を全体的に減らすことができる。

・安定でないソート

・時間計算量は難しい問題のようで、考案者のshellさんの論文では平均計算量でO(n^1.5)、最悪計算量でO(n^2)となっているとのこと。

クイックソート

・配列の中に基準値を決めて、基準値よりも小さい値をその手前に、基準値よりも大きい値をその後ろに集める。

・はじめの基準値の前後の要素群の中で、再度上記と同じ操作を繰り返す(前半と後半部分で再度基準値を決め、その前後に要素を集める)

・各回で決める基準は、なるべく真ん中の値であり続ける方が高速に処理できる

・高速に処理するための基準値の選択として、データ列から3つの要素を取得し、中央値を基準値とする方法がある。

・非安定なソート　※基準値との大小比較で2つの配列に分けられるため、元の順番が崩れることが理由

・時間計算量はO(nlogn)

・最悪時間計算量はO(n^2)　※基準値が前後どちらかの端の値であり続けると低速な処理になる

def quick_sort(data):
    #要素数が1になるまで分割されていればそのまま返す
    if len(data)<=1:
        return data
    #真ん中の要素をpivotとする
    pivot = data[len(data)//2]
    #pivotよりも小さい値と大きい値で分ける
    smaller_list = [i for i in data if i<pivot]
    bigger_list = [i for i in data if i>pivot]
    #左半分と右半分でそれぞれ再度同様の処理を行う
    left_list = quick_sort(smaller_list)
    right_list = quick_sort(bigger_list)
    #pivotを真ん中に要素として追加して返す
    return left_list + [pivot] + right_list

data = [3,5,7,9,10,4,8,6,2,1,0]    
quick_sort(data)
#[0,1,2,3,4,5,6,7,8,9,10]

def quick_sort(data):

#要素数が1になるまで分割されていればそのまま返す

if len(data)<=1:

return data

#真ん中の要素をpivotとする

pivot = data[len(data)//2]

#pivotよりも小さい値と大きい値で分ける

smaller_list = [i for i in data if i<pivot]

bigger_list = [i for i in data if i>pivot]

#左半分と右半分でそれぞれ再度同様の処理を行う

left_list = quick_sort(smaller_list)

right_list = quick_sort(bigger_list)

#pivotを真ん中に要素として追加して返す

return left_list + [pivot] + right_list

data = [3,5,7,9,10,4,8,6,2,1,0]

quick_sort(data)

#[0,1,2,3,4,5,6,7,8,9,10]

マージソート

・配列の分割と統合を繰り返すソート

・再帰的に処理を行うトップダウン方式と、非再帰的に処理を行うボトムアップ方式がある。

・トップダウン方式ではデータの2分割を繰り返す。各要素の長さが1つにまで分割しきったらソートをしつつ統合を繰り返して元の1つの配列に戻す。

・配列を用いた実装の場合、作業用領域として元のデータ以上のメモリ確保が必要。ただし、連結リストを用いることで空間計算量を小さくすることができる。

・ボトムアップ方式では、隣り合う要素2つずつをソートしつつ統合することを繰り返す。

※分割を行わない分こちらの方が操作がシンプルに思える。。。

・安定ソート　※配列の中央で左右に分割するので、元の並びが崩れないことが理由

・時間計算量はO(nlogn)。クイックソートと同じだが、マージソートの方が処理が複雑なため性能はクイックソートに劣る

def merge_sort(data):
    #要素数が1になるまで分割できたらそのまま返す
    if len(data)<=1:
        return data
    #真ん中の要素のインデックスを取得
    middle = len(data) // 2
    #左半分と右半分で分割
    left = data[:middle]
    right = data[middle:]
    #左半分と右半分でそれぞれ再度merge_sortを呼び出す
    left = merge_sort(left)
    right = merge_sort(right)
    #merge関数を呼び出しつつその結果を返す
    return merge(left, right)


def merge(left, right):
    #統合結果を保持するリスト
    result = []
    #left,rightそれぞれのインデックス
    left_index, right_index = 0, 0
    #左右のリストともに未統合の要素がある場合
    while left_index < len(left) and right_index < len(right):
        #左のリストの要素が右のリストの要素以下の場合
        if left[left_index] <= right[right_index]:
            result.append(left[left_index])
            left_index += 1
        #左のリストの要素が右のリストの要素よりも大きい場合
        else:                
            result.append(right[right_index])
            right_index += 1
    #左のリストのみ未統合の要素がある場合
    if left_index < len(left):
        #残りの要素を全て統合
        result.extend(left[left_index:])
        #reslut = result + left[left_index:]
    #右のリストのみ未統合の要素がある場合
    if right_index < len(right):
        #残りの要素を全て統合
        result.extend(right[right_index:])
        #result = result + right[right_index:]
    return result



data = [3,5,7,9,10,4,8,6,2,1,0]    
merge_sort(data)

def merge_sort(data):

#要素数が1になるまで分割できたらそのまま返す

if len(data)<=1:

return data

#真ん中の要素のインデックスを取得

middle = len(data) // 2

#左半分と右半分で分割

left = data[:middle]

right = data[middle:]

#左半分と右半分でそれぞれ再度merge_sortを呼び出す

left = merge_sort(left)

right = merge_sort(right)

#merge関数を呼び出しつつその結果を返す

return merge(left, right)

def merge(left, right):

#統合結果を保持するリスト

result = []

#left,rightそれぞれのインデックス

left_index, right_index = 0, 0

#左右のリストともに未統合の要素がある場合

while left_index < len(left) and right_index < len(right):

#左のリストの要素が右のリストの要素以下の場合

if left[left_index] <= right[right_index]:

result.append(left[left_index])

left_index += 1

#左のリストの要素が右のリストの要素よりも大きい場合

else:

result.append(right[right_index])

right_index += 1

#左のリストのみ未統合の要素がある場合

if left_index < len(left):

#残りの要素を全て統合

result.extend(left[left_index:])

#reslut = result + left[left_index:]

#右のリストのみ未統合の要素がある場合

if right_index < len(right):

#残りの要素を全て統合

result.extend(right[right_index:])

#result = result + right[right_index:]

return result

data = [3,5,7,9,10,4,8,6,2,1,0]

merge_sort(data)

ヒープソート

・安定ではないソート

・時間計算量はO(nlogn)

・クイックソート、マージソートよりは遅い。ただし、マージソートと同様データの並びに影響を受けず、常にO(nlogn)の計算量を維持できる

参考

トップページ | Programming Place Plus　アルゴリズムとデータ構造編 (programming-place.net)