私は最近、テキストの断片で最適な一致を見つけるプログラムを作成するように依頼されました。私はこのプログラムをうまく書きましたが、その時間の複雑さについて質問があります。
問題は次のように定義されます。
クエリが与えられた場合、ドキュメント内のクエリ ワードの出現箇所を見つけて、最適なトークンを強調表示します。
私のプログラムにかかる時間
O(m + n + p)
ここ
m = ドキュメントの長さ (文字数)
n = クエリの長さ (文字数)
p = ドキュメント内の一致の合計数
この場合、最大の用語は常に「m」になります。ほとんどの場合、ドキュメントはクエリ自体よりも大きくなるためです。
私のプログラムの時間計算量は O(m) であると安全に推測できますか?
いいえ、できません。Big-O 表記法によると、実際の時間などの定数がある場合、関数mはアルゴリズムの実行にかかる実際の時間の上限であり、M常に以下になりM*mます。ドキュメントのサイズが 0 (空のドキュメント) であるにもかかわらず、誰かが正の文字数でクエリを実行したとします。この場合の上限は0(プラス定数) になりますが、実際のプログラムの実行時間はそれよりも長くなる可能性があります。したがって、あなたのプログラムは とは言えませんO(m)。
言い換えれば、「ほとんどの場合」では十分ではありません。すべての場合において、アルゴリズムがその上限内で機能することを証明する必要があります。
更新:についても同じことが言えますp: 常識ではpは常に よりも小さいと言われてmいますが、それは検索用語が重複しない場合にのみ当てはまります。たとえば、ドキュメントaaaaaa(m=6) と検索語a,aaおよびaaa(n=3) を考えてみましょう。この場合、 が 6 回、 がa5 回、 がaa4回出現aaaするので、p = 15. これは非常にありそうもないシナリオですが (空のドキュメントでも同じです) p、複雑さの分析で考慮する必要があります。したがって、O(m + n + p)最初に述べたように、プログラムを実際に記述する必要があります。
私のプログラムにかかる時間: O(m + n + p) まず最初に、それがあなたのプログラムにかかる時間だとはまったく信じていません。
クエリを解析して、ドキュメント内の単語を検索するよう求められます。これは複雑な相互参照の問題です。複数の単語に含まれる文字が、ドキュメント内にランダムに配置された同じシーケンスと正確な文字シーケンスで一致する必要があるためです。ほとんどの学生はこれのハッシュを作成し、最初の単語を取得してドキュメントをスキャンしてその単語の出現箇所を探し、次と次と次で同じことを行うことで、N 乗プロセスを作成します。ドキュメントの内容と単語を相互参照する効果的な手段を開発する必要があります。そうしないと、N^2 プロセスが作成されます。オフハンドでは、クエリで単語の辞書を作成し、ドキュメントを単語に解析し、検索する単語の辞書と照合します。それはmLognになります
m = number of words the document
n = number of words in the dictionary you create in an nLogn process.
あなたは私が書いた記事で言及されました。これは、同様の、しかしはるかに複雑な単語一致の問題を解決するためです。
http://www.codeproject.com/Tips/882998/Performance-Solving-WonderWord-パズル
あなたの最初の回答者は、ブレークを使用せずに文字を見つける必要はなかったと仮定しながら正しかったが、彼の O 記法は間違っていると信じている。