1

我目前无法识别和理解以下算法的复杂时间。

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

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

谢谢。

4

1 回答 1

0

我只是在重复阿米特所说的话，所以如果你清楚的话，请给他投票 - 我觉得这个解释有点令人困惑。

您的平均复杂度为 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)。

于 2012-04-29T01:18:09.217 回答