大O表示法-使用HashSet查找的循环的正确定义 [英] Big O Notation - Correct definition for a loop with HashSet lookup

问题描述

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

From my understanding, a simple for loop will have a complexity of O(n).

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

如果我在foreach中引入哈希查找，是否会将复杂度保持为O(n)?

If I introduce a Hash lookup within the foreach, will that keep the complexity to O(n)?

var ids = new HashSet<int>();

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

同样，如果HashSet而是一个列表，那会使O(n ^ 2)变得复杂吗?

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

var ids = new List<int>();

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

我正在从这个问题中收集 HashSet的查找时间复杂度< T>(IEqualityComparer< T> )?，并希望确保我的理解是正确的.请添加您认为对理解Big-O术语有用的其他信息.

I was gleaning from this question What is the lookup time complexity of HashSet<T>(IEqualityComparer<T>)? , and would love to make sure my understanding is correct. Please add any additional info that you think would be useful to understanding Big-O terminology.

推荐答案

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

Your interpretation is correct, hash look-up is O(1), so repeating it n times give you an O(n) complexity.

对于具有正确实现的哈希码的对象，哈希查找是恒定时间(即O(1)).由于您使用的是int(哈希码本身就是数字)，因此可以实现很好的实现，从而确保恒定的访问时间.

Hash lookup is constant time (i.e. O(1)) for objects with properly implemented hash code. Since you are using an int, for which the hash code is the number itself, you get a very good implementation, ensuring constant-time access.

如果HashSet是一个列表，那么是否会使O(n ² )变得复杂?

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

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

Technically, it would be O(n*m), where m represents the number of items in the id list.

这篇关于大O表示法-使用HashSet查找的循环的正确定义的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！