四十三庵

蔀の雑記帳

Dijkstra Algorithm

有向グラフの最短経路を見つけるためのアルゴリズム 計算コストはO(N2) 経路コストの計算にヒープを使うと、約O(2NlogN)までパフォーマンスが改善する 節点と辺の数が同程度の時に限るらしい 辺が多くなる(例えば全ての節点がつながれた完全グラフの時)は…

Warshall–Floyd Algorithm

ダイクストラと発想は同じだが、出発点が存在せず、全ての節点と全ての接点のコストテーブルを更新する コストテーブルのサイズはN*N 計算量はO(N3) 計算量はダイクストラよりN回倍多いが、実装が楽で、接点を結ぶ辺が多い際は有効 実装 import Foundation l…

グラフ理論

前提 本を読んだだけだと、グラフ理論そのものがよくわらかなかったので、前提を調べた。 内容 最終的なアウトプットが表になるかTreeになるかでわかれる グラフ理論では頂点のことをVertex、辺のことをEdgeと呼ぶ慣習があるよう。 Vertex = Node, Edge = li…

Bucket Sort

要素のとりうる値の範囲(バケット)に応じて挿入して、最後にmapするようなSort方法 特定の条件では計算効率がよい場合がある バケットがm個のとき、m < NならO(N)になる。

Heap Sort(ヒープソート)

Heapを使ってSortする Performance of heap sort is O(n log n) in best, worst, and average case 実装 Heapの実装にどっかバグがあって、上手くソートできなかった。 一日格闘してダメだったので、SACの模範解答見てお茶を濁した。 import Foundation stru…

Merge Sort(マージソート)

最悪計算量でもO(NlogN) メモリ領域はO(N)分食う フォンノイマンが考えたアルゴリズムらしいが、考え方はシンプルだし、計算効率いいし実用的 配列の真ん中から要素を分けて、それを繰り替えして、要素二つにしたらmerge() mergeされた配列は再帰的にどんど…

Quick Sort(クイックソート)

配列の最初の要素と二番目の要素の大きい方をpivotとして、その値との大小関係を使ってSortする 計算量は平均でO(NlogN) 最悪の場合はO(N2) 本の通り実装しようとしたら、Arrayはstructなので再帰ができなくて、 しかも引数のArrayはimmutabelで直接操作でき…

Bubble Sort(バブルソート)

小さな泡が水から浮き上がるようにソートすることから 「配列の最後からその一個前の要素を大小比較して、逆だったら要素を入れ替える」という操作を最初の要素の一個前まで行うことで最小の要素が配列の最初になる その操作を次は最初の要素の二個前まで行…

Hash

ハッシュ値を使うとO(1)で値を求められる 衝突という問題がある 衝突を回避するためには二つ方法がある チェイン法(chaining mechanism) 衝突した値はリスト構造でenqueして格納する 開番地法(open addressing) 衝突したら再ハッシュを行い、空いている…

B Tree(B木)

ノート balanced treeの例 A B-Tree of order n satisfies the following properties: Every node has at most 2n keys. Every node (except root) has at least n keys. Every non-leaf node with k keys has k+1 children. The keys in all nodes are sort…