Big O Notation - 使用 HashSet 查找的循环的正确定义

Question

据我了解，一个简单的 for 循环的复杂度为 O(n)。

foreach(var record in records) {
   // ...
}

如果我在 foreach 中引入一个 Hash 查找，这会把复杂度保持在 O(n) 吗？

var ids = new HashSet<int>();

foreach(var record in records) {
   bool isRecordInIdSet = ids.Contains(record.id);
}

同样，如果 HashSet 是一个列表，那么复杂度是否会达到 O(n^2)？

var ids = new List<int>();

foreach(var record in records) {
   bool isRecordInIdSet = ids.Contains(record.id);
}

我正在收集这个问题 What is the lookup time complexity of HashSet<T>(IEqualityComparer<T>)? ，很想确保我的理解是正确的。请添加您认为对理解 Big-O 术语有用的任何其他信息。

Answer 1

您的解释是正确的，哈希查找是 O(1)，因此重复 n 次会给您带来 O(n) 的复杂性。

对于具有正确实现的哈希码的对象，哈希查找是常数时间（即 O(1)）。由于您使用的是 int，哈希码就是数字本身，因此您获得了一个非常好的实现，确保了恒定时间访问。

if the HashSet was instead a list, would that make the complexity to O(n²)?

从技术上讲，这将是 O(n*m)，其中 m 表示 id 列表中的项目数。

Answer 2

您对 list 与 hashmap 的分析是正确的。

var ids = new HashSet<int>();

foreach(var record in records) {
   bool isRecordInIdSet = ids.Contains(record.id); // this is O(1)
}

哈希表具有恒定的查找时间 ( O(1) )。这样for循环的时间复杂度为O(n)，其中n为记录数

var ids = new List<int>();
foreach(var record in records) {
   bool isRecordInIdSet = ids.Contains(record.id); // this is O(m), where m is the size of list ids
}

当使用列表时，你的.Contains方法有O(n)的时间，因为在最坏的情况下你要找的项目在列表的最后，所以你必须遍历整个列表并使n -1 比较。实际上，您不必每次都这样做，但请记住，Big-O 表示法关注的是最坏的情况。如果 ids 列表和记录列表的大小取决于同一个变量，那么这个 for 循环的复杂度为 O(n^2)。否则，它将是 O(n * m)，其中 n 是记录的大小，m 是 id 的大小。

Big O Notation - 使用 HashSet 查找的循环的正确定义

Big O Notation - Correct definition for a loop with HashSet lookup

.net

big-o

computer-science