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 不允许重复。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 回答