算法复杂度时间

Question

我目前在识别和理解以下算法的复杂性时间方面遇到了困难。

背景:有一个文件列表，每个文件都包含一个候选人Ids列表。文件的数量和其中的候选人数量都不是固定的。

如何计算算法的时间复杂度，该算法负责:读取每个文件并将所有唯一的候选Ids添加到Hashset中？

谢谢。

Answer 1

我只是重复一下阿米特所说的话，所以如果你清楚的话，请给他投赞成票--我觉得这个解释有点混乱。

您的平均复杂度为O(n)，其中n是(来自所有文件的)候选的总数。因此，如果你有a文件，每个文件都有b候选者，那么所花费的时间与a * b成正比。

这是因为解决问题的最简单方法是简单地遍历所有数据，将它们添加到集合中。该集合将在必要时丢弃重复项。

循环遍历所有值所需的时间与值的数量(即O(n)部分)成比例。将一个值添加到哈希集需要固定的时间(或O(1))。因为这是每个条目的固定时间，所以您的总时间仍然是O(n)。

然而，哈希集有一种奇怪的最坏情况下的行为-在某些(不常见的)情况下，它们需要的时间与内容的大小成比例。因此，在最坏的情况下，每次添加一个值都需要O(m)工作量，其中m是集合中的项数。

现在m是(大约-它从零开始，直到...)不同值的数量。因此，我们有两种常见的情况：

• 如果不同的候选者的数量随着我们阅读的次数的增加而增加(例如，90%的文件总是新的候选者)，那么m与n成正比。这意味着添加每个候选者的工作量与n成比例增加。因此，总工作量与n^2成比例(因为对于每个候选者，我们做的工作与n成比例，并且有n个候选者)。所以最坏的情况是O(n^2)，

，

• ，如果不同的候选者的数量实际上是固定的，那么当你读取越来越多的文件时，它们往往都是已知的候选者。在这种情况下，插入到集合中的额外工作是恒定的(对于唯一的候选者，您只会获得固定次数的奇怪行为-它不依赖于n)。在这种情况下，当n越来越大时，集合的性能不会继续变差，因此最坏情况下的复杂度仍然是O(N)。