1

可能的重复：
算法的时间复杂度

在计算以下算法的时间复杂度时，我的解释是否正确？

  • 一个 HashSet，moduleMarksheetFiles，用于添加包含指定 moduleName 的文件。-marksheetFiles 是一个哈希集。-如果模块是“数学”，那么任何带有模块“数学”的标记表都会添加到 HashSet。

    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

0 回答 0