时间复杂度的算法 [英] Time Complexity for an algorithm

问题描述

难道计算以下算法的时间复杂度，当我纠正我的解释？

Am I correct in my explanation when calculating the time complexity of the following algorithm?

• 一个HashSet的，moduleMarksheetFiles，被用来添加包含指定的模块名的文件。

• A HashSet, moduleMarksheetFiles, is being used to add the files that contain the moduleName specified.

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

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

令m文件的数量

Let m be the number of files

因此​​，平均时间复杂度为：O（（M * K）^ 2）

Therefore, the average time complexity would be: O((m*k)^2).

这是正确的？

此外，你将如何计算最坏的情况下？

Also, how would you calculate the worst case?

感谢。

PS。这不是功课，只是我的分析系统的算法进行性能评估。

PS. It is not homework, just analysing my system's algorithm to evaluate performance.

推荐答案

没有，这不是平方，这是O（NK）。 （从技术上讲，这意味着它的也的O（（NK）2），但我们并不关心。）

No, it's not squared, this is O(nk). (Technically, that means it's also O((nk)²), but we don't care.)

您的误解是，它的HashSet的最坏情况下的性能是最重要的位置。然而，即使一个哈希表可能有最坏情况O（n）的插入时间（如果需要老调重弹的每一个元素），它的 摊销的插入时间是O（1）（假设你的散列函数表现良好; File.GetHash code presumably是）。换句话说，如果你插入多的事情，所以很多人会为O（1）偶尔O（n）的插入也无所谓。

Your misconception is that it the worst-case performance of HashSet is what counts here. However, even though a hashtable may have worst-case O(n) insertion time (if it needs to rehash every element), its amortized insertion time is O(1) (assuming your hash function is well behaved; File.GetHashCode presumably is). In other words, if you insert multiple things, so many of them will be O(1) that the occasional O(n) insertion does not matter.

因此​​，我们可以把插入作为恒定时操作，所以性能由迭代穿过内循环体的数量，这是O（NK）纯粹口授

Therefore, we can treat insertions as constant-time operations, so performance is purely dictated by the number of iterations through the inner loop body, which is O(nk).

这篇关于时间复杂度的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！