1

次のアルゴリズムの時間計算量を計算するときの説明は正しいですか?

  • HashSet である moduleMarksheetFiles は、指定された moduleName を含むファイルを追加するために使用されています。

    for (File file: marksheetFiles){
     while(csvReader.readRecord()){
         String moduleName = csvReader.get(ModuleName);

         if (moduleName.equals(module)){
               moduleMarksheetFiles.add(file);
         }
     }
 }

  • m をファイル数とする

  • k をファイルあたりの平均レコード数とします。
  • HashSet では重複が許可されないため、各ファイルは 1 回だけ追加されます。HashSet.add() は平均で O(1)、最悪の場合は O(n) です。
  • 指定された moduleName を持つレコードを検索するには、ファイル内のすべてのレコードを moduleName と比較する必要があり、O(n) ステップかかります。

したがって、平均時間計算量は O((m*k)^2) になります。

これは正しいです？

また、最悪のケースをどのように計算しますか?

ありがとう。

PS。宿題ではなく、システムのアルゴリズムを分析してパフォーマンスを評価するだけです。

4

1 に答える 1

2

いいえ、二乗ではありません。これは O(nk) です。(技術的には、これはO((nk)²)でもあることを意味しますが、気にしません。)

あなたの誤解は、HashSet の最悪の場合のパフォーマンスがここで重要であるということです。ただし、ハッシュテーブルの最悪の場合の O(n) 挿入時間 (すべての要素を再ハッシュする必要がある場合) がある場合でも、その償却挿入時間は O(1) です (ハッシュ関数の動作が適切であると仮定すると、File.GetHashCodeおそらくそうです)。つまり、複数のものを挿入すると、それらの多くが O(1) になるため、たまに O(n) 挿入しても問題になりません。

したがって、挿入を一定時間の操作として扱うことができるため、パフォーマンスは、O(nk) である内側のループ本体の反復回数によって純粋に決定されます。

于 2012-04-29T12:11:38.013 に答える