KMP法の効率
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2012/07/29 10:36 UTC 版)
「クヌース-モリス-プラット法」の記事における「KMP法の効率」の解説
このアルゴリズムの各部分は（上述の通り）それぞれ O(k) と O(n) の計算量があるので、全体としての計算量は O(n + k) となる。 先述の実施例でも明らかなように、文字をスキップできればできただけ単純な文字列検索アルゴリズムよりも有利となる。つまり、バックトラックがない方が好ましい。換言すれば T が全て 0 になっていればよい。従って "ABCDEFG" のような単語ではこのアルゴリズムは最も効率的に動作し、その際のテーブルは先頭が -1 でそれ以外は全て 0 となっている。逆に W = "AAAAAAA" のような場合は最悪である。このときのテーブルは以下のようになる。 i0 1 2 3 4 5 6 W[i]A A A A A A A T[i]-1 0 1 2 3 4 5 これは T の最悪のパターンであり、S = "AAAAAABAAAAAABAAAAAAA" といった単語にもあてはまる。S の中に "AAAAAAB" が出現する頻度が多いほど繰り返し回数が増える。この単語のテーブル生成は高速となるが、検索は複数回行われる可能性があるのに対して、テーブル生成は1回だけである。従って、このような単語を検索する場合、このアルゴリズムの性能は低下する。ちなみに、このような文字列はボイヤー-ムーア法では最高の性能となる。KMP法は最良でも最悪でも線形時間で検索が完了するのに対して、ボイヤー-ムーア法は最良と最悪で大きく時間が異なる。
※この「KMP法の効率」の解説は、「クヌース-モリス-プラット法」の解説の一部です。
「KMP法の効率」を含む「クヌース-モリス-プラット法」の記事については、「クヌース-モリス-プラット法」の概要を参照ください。
KMP法の効率
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/09/08 01:52 UTC 版)
「クヌース–モリス–プラット法」の記事における「KMP法の効率」の解説
このアルゴリズムの各部分は（上述の通り）それぞれ O(k) と O(n) の計算量があるので、全体としての計算量は O(n + k) となる。 先述の実施例でも明らかなように、文字をスキップできればできただけ単純な文字列検索アルゴリズムよりも有利となる。つまり、バックトラックがない方が好ましい。換言すれば T が全て 0 になっていればよい。従って "ABCDEFG" のような単語ではこのアルゴリズムは最も効率的に動作し、その際のテーブルは先頭が -1 でそれ以外は全て 0 となっている。逆に W = "AAAAAAA" のような場合は最悪である。このときのテーブルは以下のようになる。 i0 1 2 3 4 5 6 W[i]A A A A A A A T[i]-1 0 1 2 3 4 5 これは T の最悪のパターンであり、S = "AAAAAABAAAAAABAAAAAAA" といった単語にもあてはまる。S の中に "AAAAAAB" が出現する頻度が多いほど繰り返し回数が増える。この単語のテーブル生成は高速となるが、検索は複数回行われる可能性があるのに対して、テーブル生成は1回だけである。従って、このような単語を検索する場合、このアルゴリズムの性能は低下する。ちなみに、このような文字列はボイヤー-ムーア法では最高の性能となる。KMP法は最良でも最悪でも線形時間で検索が完了するのに対して、ボイヤー-ムーア法は最良と最悪で大きく時間が異なる。
※この「KMP法の効率」の解説は、「クヌース–モリス–プラット法」の解説の一部です。
「KMP法の効率」を含む「クヌース–モリス–プラット法」の記事については、「クヌース–モリス–プラット法」の概要を参照ください。
- KMP法の効率のページへのリンク
