搜索列表中的记录而不扫描所有记录
我有一个像这样的记录（结构）列表：
struct Rec
{
int WordID;
int NextID;
int PrevID;
}
List<Rec>= New List<Rec>(){...};
我需要一种方法来查找列表中“Rec”类型的值，而无需像二分搜索那样搜索所有记录。我希望它的时间复杂度小于 O(n)
I have a List of an Record(structure) like this :
struct Rec
{
int WordID;
int NextID;
int PrevID;
}
List<Rec>= New List<Rec>(){...};
I need a way to find a value of "Rec" type in List without search all of records like Binary search. I want it's time complexity be less than O(n)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
在列表中搜索项目的最佳方法当然不是使用列表，而是使用哈希表。
如果您有字典而不是列表（或字典和列表），则可以在平均\摊销 O(1) 中搜索精确值。
您还可以使用二分搜索，但前提是列表已排序，有方法
List.BinarySearch 且搜索时间复杂度为 O(log n)。对包含 n 个项目的列表进行排序的时间复杂度为 O(n log n)。
在哈希表中插入 n 个项目的平均时间复杂度为 O(n)，插入一个项目的平均时间复杂度为 O(1)。
这意味着创建哈希表（或使哈希表与列表保持同步）将比对列表进行排序更快。
然而，请考虑哈希表会消耗更多内存，因为它们必须在内部保留一个存储桶数组。
The best way to search for an item in a list is of course not having a list but having an hashtable.
If you have a dictionary instead of a list (or a dictionary AND a list) you can perform search for exact values in averaged\amortized O(1).
You can also use a binary search but only if the list is sorted, there is the method
List<T>.BinarySearchand the search with be O(log n).Sorting a list with n items is O(n log n).
Inserting n items in an hashtable instead is averaged O(n), inserting an item is averaged O(1).
This means that also creating the hashtable (or keeping the hashtable synchronized with the list) will be faster than sorting a list.
Consider however that hashtable consumes more memory because they have to keep internally a bucket array.
如果您的列表已排序，您可以使用二分搜索。
You can use binary search providing your list is sorted.