排序 std::list 中搜索的复杂度是多少? [英] What is the complexity of search in sorted std::list?

问题描述

在已排序的 std::list 中搜索的复杂度是多少?我知道如果数据结构具有随机访问，则在排序数据中搜索的复杂性是 O(log n).但是既然列表没有随机访问，那么排序时的复杂度是多少?

What is the complexity of search in sorted std::list? I knew that complexity of search in sorted data is O(log n) if the data structure has random access. But since list doesn't have random access, what is it's complexity when it is sorted?

推荐答案

好吧，这是 O(N).在 std::list 中搜索总是 O(N)，排序与否.

Well, it's O(N). Search is always O(N) in a std::list, sorted or not.

排序集合很有帮助，因为您可以知道您是否离得太远或不够.但既然你只能从列表的一端开始，那也无济于事.

Sorted collections help because you can know if you're too far, or not enough. But since you can't start anywhere but at one end of a list, it won't help.

这篇关于排序 std::list 中搜索的复杂度是多少?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！