No.2ベストアンサー
- 回答日時:
> (1)
メインな文字列の検索処理についてみると、テキストの個々の文字について1回しか比較を行いませんから、O(N)になります。
ですが、KMPではその前にテーブルを作る必要があります。こちらの処理はO(M)になります。
両方あわせるとO(M+N)です。
> (2)
文字列検索をするためには、「テキストの全ての文字を調べる」必要があり、そのためには最低でもO(N)は必要です。
O(N)より小さい、O(log N) や O(√N) では、全ての文字を調べることができません。
同様に、検索パターンの方も全ての文字を調べる必要があるから、こちら側では最低でもO(M)が必要です。
つまり、両方あわせると、最低でもO(M+N)は必要、ということになります。
この回答へのお礼
お礼日時:2008/12/22 17:44
テーブルを作る処理と比較の処理を別々に考えたら納得できました。
(2)についてもとても分かりやすい説明ありがとうございます。
解決できました!
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 建設業・製造業 河川の積算の勉強に役立つ本はありませんか? 例えば数量計算書や図面から間違いがないか確認し、 確認後 2 2023/02/09 19:40
- Excel(エクセル) エクセルのSUM関数について 4 2023/04/18 10:37
- 経済学 国の予算原則について質問です。 「予算単年度主義」と「会計年度独立の原則」の違いが今ひとつ分かりませ 1 2022/04/08 15:53
- その他(悩み相談・人生相談) そろばんのことで質問です 割りきれないわり算のことでおしえてください 例えば、93÷7の計算です そ 2 2022/07/18 15:18
- その他(法律) 有給金額の計算について 5 2023/06/23 17:44
- その他(ソフトウェア) F-BASICで計算中の実行が中途で勝手に止まり、大変困っています。 2 2023/03/02 16:15
- Excel(エクセル) IFERROR(IF()IF())のような形の構文が作れません 2 2023/02/05 17:51
- C言語・C++・C# C言語 3 2022/10/04 15:07
- 統計学 QC検定2級合格に向け、現在勉強しています。教材のテキストの中で不適合品率に関する検定の例題が出題さ 2 2023/08/16 22:58
- Excel(エクセル) Excelの計算式で質問です。 3 2022/06/21 21:58
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
数値計算の高速化 (cos, sin, exp)
-
Perlでのルートの計算
-
Vb6.0で三角関数が使えない
-
VBAの再計算が反映されない件に...
-
Visual C++でdebugとreleaseで...
-
[急募]Pythonについてです。
-
R言語での極小値の指数形式での...
-
スライムがつぶれていく様子を...
-
60進数の四則計算
-
VB6.0でのバイナリデータの扱い...
-
傾いた四角形内の範囲の条件式
-
EXCELなどで「返す」という表現
-
VB6で正確なミリ秒を計測したい...
-
CとFORTRANの計算速度はどちら...
-
Excel VBAの残業時間の合計計算...
-
VBでReplace
-
10進数から8進数へ
-
順列のプログラムについて(VB)
-
Javascrptの0の掛け算
-
エクセルで特定のセルのみを任...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
65536は2の何乗なのでしょうか?
-
VBAの再計算が反映されない件に...
-
排他的論理和 BCC(水平パリテ...
-
EXCELなどで「返す」という表現
-
C言語の課題で、1年の秒数を計...
-
バッチファイルでウインドウを...
-
骨折リスク評価のFRAXについて...
-
変化させるセルが変化しない
-
CとFORTRANの計算速度はどちら...
-
なぜオーバーフローになるので...
-
数値計算の高速化 (cos, sin, exp)
-
モジュラス103の計算とは何でし...
-
C# 計算処理中に実行中ウィン...
-
モジュロ
-
引き放し法による除算アルゴリ...
-
60進数の四則計算
-
C言語についてです。 再帰を使...
-
Perlで時間の計算
-
CRC8を教えてください
-
傾いた四角形内の範囲の条件式
おすすめ情報