四十三庵

蔀の雑記帳

データ構造とアルゴリズム

アルゴリズム設計法

目次 目次 brute force solution Dynamic Programming Solution(動的計画法) 分類 Divide and conquer solution (分割統治法) Greedy Method(欲張り法) brute force solution 日本語の訳語がない セキュリティの文脈ではよくブルートフォースアタック…

Boyer-Moore String Search

理想的な場合はO(N/M)で探索できる 検索対象のワードの右から順に探索することで、スキップ量を大きくする

Knuth-Morris-Pratt String Search

単純な文字列検索は検索対象の文章の長さNと検索ワードの長さMのO(MN)になる KMPアルゴリズムを使うとO(N)でいける ただし検索ワードのスキップ量があらかじめ設定されている場合 発想としては、検索対象の文字を一文字ずつ照合していくと、 実は明らかにス…

Kruskal's Algorithm

実装 func minimumSpanningTreeKruskal<T>(graph: Graph<T>) -> (cost: Int, tree: Graph<T>) { var cost: Int = 0 var tree = Graph<T>() let sortedEdgeListByWeight = graph.edgeList.sorted(by: { $0.weight < $1.weight }) var unionFind = UnionFind<T>() for vertex </t></t></t></t></t>…

Prim’s Algorithm

計算量はO(n2) 解説はここがわかりやすかった 実装 func minimumSpanningTreePrim<T>(graph: Graph<T>) -> (cost: Int, tree: Graph<T>) { var cost: Int = 0 var tree = Graph<T>() guard let start = graph.vertices.first else { return (cost: cost, tree: tree) } v</t></t></t></t>…

Minimum Spanning Tree

重み付けのあるグラフに対して、コストが最小となるスパニングツリーを求めるアルゴリズム。 Prim’s Algorithm / Kruskal's Algorithmが二大解法

BFSとDFS

Breadth-First Search: 幅優先探索 Depth-First Search: 深さ優先探索 BFSは開始するNodeをキューに入れ、一度デキューしてから、隣接するNodeをキューイングする。 そしてDequeueしたNodeの隣接しているNodeをenqueueする…… (一度enqueueしたNodeはもうenq…

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…

AVL Tree

ノート ソビエト連邦時代のロシア人が論文書いたデータ構造。 平衡木の例 回転処理で計算量の効率性を保つ 実装例までは追えず

2-3 Tree(2-3木)

ノート balanced tree(平衡木)の例として2-3木が紹介されている 二分探索木はあくまで平均の計算量がO(logN)となるだけで、操作の結果によっては最悪の計算量O(N)になりうる そこでbalanced treeは常に計算量がO(logN)となるように要素を挿入・削除するた…

Binary Search Tree(二分探索木)

BSTとは 任意の要素の取得がO(logN)で済む構造 計算量がO(logN)ですむ証明が難しかった 実装 最初Structでやろうとしたら、再帰にできなくて死んだ ただ再帰でやることを思いついてしまうと、実装時間としてはそんなにかかんなかった if文2回ネスト(2×2)す…

Heap

基本教科書を読んでわかることは書かなくて、読んでいてわからなかった点や、 実際に手動かして書いてみたコードなんかを書いています。 Heapとは www.raywenderlich.com ここの説明がわかりやすい。 英語の意味 英語のHeapの意味は積み重ね heap of moneyな…

なぜデータ構造とアルゴリズムを学ぶか

2020/2〜3月にデータ構造とアルゴリズムを勉強したので、その勉強ノートをブログで公開して行こうと思う。 下記の本を使いました。 目次 目次 方法と期間 目的 技術力とは? フレームワークがあれば不要だよ論 次回予告 方法と期間 五十嵐健夫さんの…

データ構造とアルゴリズムノート 目次

2020/2〜3月にデータ構造とアルゴリズムを勉強したので、その勉強ノートをブログで公開する。 全体 はじめに データ構造とアルゴリズムノート 目次 なぜデータ構造とアルゴリズムを学ぶか データ構造 Heap Binary Search Tree(二分探索木) 2-3 Tree…