アルゴリズム | ページ 9

[Python] 決定性有限オートマトンを使った文字列検索

以下の続きです。下の動画を参考にしています。決定性有限オートマトンを使うと、文字列検索アルゴリズムは以下の流れで表現できます。オートマトンを作るあるパターン\( P \)が与えられたとして、そのパターンに...

決定性有限オートマトンを使った文字列検索のアルゴリズムを書くために、決定性有限オートマトンについてまずは考えます。決定性有限オートマトン（けっていせいゆうげんオートマトン、英:Deterministic Finite Automaton）または決定性有限状...

ラビン-カープ法テキストの中からパターンを探すときに、パターンのハッシュと検索箇所のハッシュが一致するかどうかを比較して検索を行います。ハッシュの時間計算量が \(O(m)\) の場合は、アルゴリズム全体の計算量が \(O(m \times n) \) ...

与えられた文字列の中から、パターンに一致する部分を総当たりで探します。時間計算量は \( O(n \times m) \)、空間計算量は\( O(1) \) になります。 import random import string def match_pa...

内挿探索 2分探索ではリストの中央の値を基準として探索を行いますが、内挿探索は、この基準の決め方を工夫することで、探索をより効率的に行おうとする検索方法です。要素が均一に分布している場合は、内挿探索は平均して\(log（log（n））\)、最悪の場合、最大...

2分探索二分探索（にぶんたんさく、英: binary search、BS）やバイナリサーチとは、ソート済み配列に対する探索アルゴリズムの一つ。出典: フリー百科事典『ウィキペディア（Wikipedia）』ソート済みのリストにおいて、目標との中央...

線形探索線形探索（せんけいたんさく、英:linear search, sequential search）は、検索のアルゴリズムの一つ。リストや配列に入ったデータに対する検索を行うにあたって、先頭から順に比較を行い、それが見つかれば終了する。出典: フリ...

Python でヒープソートを実装します。ヒープソートヒープソート(heap sort) とはリストの並べ替えを二分ヒープ木を用いて行うソートのアルゴリズムである（ヒープ領域とは無関係であることに注意する）。出典: フリー百科事典『ウィキペディア（Wiki...

Python でシェルソートを実装します。シェルソートシェルソート（改良挿入ソート、英語:Shellsort, Shell sort, Shell's method）は、in-placeな比較ソートのアルゴリズムの一種である。シェルソートは、交換によるソート（...

プリム法を用いて、重み付き無向グラフの最小全域木を求めます。プリム法はダイクストラ法とほぼ同じで、コードもダイクストラ法のものをほぼ流用しています。全域木全域木とは、グラフの中の全ての頂点を使って作られる木のことです。全域木（ぜ...