このアプローチの時間の複雑さ

私は2つのファイルを読み込み、それぞれの行を2つの異なるリストにそれぞれ保存しています。今度は、最初のリストの文字列が2番目のリストにあるかどうかをチェックする必要があります。このアプローチの時間の複雑さ

File1_visited [ストリング]真

File2_visited [文字列] = TRUE = -

通常の比較では、これは（N^2）

しかしようなグラフベースのデータ構造を使用してはOを取ります。

両方が真であるかどうかを確認できます。文字列は両方のファイルに存在します。これはO（n）になります。

私は時間の複雑さを減らすことができ、私の理解は正しいのですか？

例シナリオ -

File1-

テキスト1テキスト2 テキスト3 Text4

ファイル2 -

Text5 Text7 テキスト1テキスト2

これら2つのファイルを比較します。

出典

2016-07-22 Ryo

分析ミスの主なものは、「グラフ構造の構築とアクセスに要する時間の複雑さは何ですか？」です。シンプルで効率的な方法は、両方のファイルをハッシュセットにロードし、次に交差をチェックすることです。これはあなたのアプローチによく似ていますが、作成とアクセスに非常に効率的な標準構造を使用しています。ファイルの大きさはどれくらいですか？ – jpmc26

最大1000行と仮定します。また、2つのアプローチに関して正しい理解ができました。私はハッシュセットを考えましたが、各ファイルを1回ずつ処理する必要があるため、2番目のアプローチと同じではありません – Ryo

データセットが1000行だけの場合、なぜO（n）を気にしますか？ Big O Notationは、本当に大きな数値/計算セットです。 https://en.wikipedia.org/wiki/Big_O_notation –

はい、O(n^2)からO(n)になりました。あなたは空間の複雑さを調べることもできますが、一方のグラフを保存しなければならず、もう一方のグラフのスペースを少なくする必要があります。 HashMapは、メモリを気にしなければこのような状況に適していますし、実装が簡単な場合は他の配列にも適しています。

出典

2016-07-22 18:41:59 MathBunny

まあ、技術的に 'O（n + m）'、それは 'HashMap'を想定していますが、OPは*"グラフベースのデータ構造 "*を使用して、' TreeMap'を意味し、 'O（（n OPのような第2のマップを作成するのではなく、第1のファイル（「n」）がマップにロードされ、第2のファイル（「m」）がマップをチェックするためにのみ使用されると仮定すると、実際に言った。 – Andreas

このアプローチの時間の複雑さ

答えて

関連する問題