テーブル生成法の効率
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/09/08 01:52 UTC 版)
「クヌース–モリス–プラット法」の記事における「テーブル生成法の効率」の解説
テーブル生成アルゴリズムの計算量は O(n)（ここで n は W の長さ）である。初期化コードを除くと処理は全て while ループ内で行われるので、このループを O(n) 回実行することを示せばよい。これは i と i - j の値を考えていくことで明らかとなる。第一の分岐では i - j は変化せず、i と j が同時にインクリメントされる。第二の分岐では j が T[j] で置換される。これは既に述べたように j より常に小さい。従って i - j は増加する。第三の分岐では、i だけがインクリメントされる。つまり、i も i - j も増加する。i ≥ i - j であるので、これは各段階で i か i の下限が増加するのと同じことである。このアルゴリズムは i = n となったとき終了し、i - j の初期値は 1 なので、ループは最大で 2n 回くりかえされる。以上からテーブル生成アルゴリズムの計算量は O(n) となる。
※この「テーブル生成法の効率」の解説は、「クヌース–モリス–プラット法」の解説の一部です。
「テーブル生成法の効率」を含む「クヌース–モリス–プラット法」の記事については、「クヌース–モリス–プラット法」の概要を参照ください。
ウィキペディア小見出し辞書の「テーブル生成法の効率」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- テーブル生成法の効率のページへのリンク
