算法复杂度：为什么排序可以将复杂度降低到 O(log n)
我正在阅读一些有关算法复杂性的文本（我打算稍后参加算法课程），但我不明白以下内容。
假设我必须在无序列表中搜索某个项目，则查找该项目所需的步骤数将与该列表中的项目数成正比。在包含 10 个项目的列表中查找它可能需要 10 个步骤，而在包含 100000 个项目的列表中查找它可能需要 100000 个步骤。因此算法复杂度是线性的，用“O(n)”表示。
现在，此文本 [1] 告诉我，如果我要按某些属性（例如社会安全号码）对列表进行排序，查找项目的算法复杂度将减少到 O(log n)，这要快得多，关闭课程。 现在我可以看到在 b 树的情况下会发生这种情况，但是这如何应用于列表呢？由于英语不是我的母语，我是否误解了文本？
[1]http://msdn.microsoft.com/en-us/library/ms379571.aspx
I'm reading some texts about algorithmic complexity (and I'm planning to take an algorithms course later), but I don't understand the following.
Say I've to search for an item in an unordered list, the number of steps it takes to find it would be proportional to the number of items on that list. Finding it in a list of 10 items could take 10 steps, doing the same for a list of 100000 items could take 100000 steps. So the algorithmic complexity would be linear, denoted by 'O(n)'.
Now, this text[1] tells me if I were to sort the list by some property, say a social security number, the algorithmic complexity of finding an item would be reduced to O(log n), which is a lot faster, off course.
Now I can see this happening in case of a b-tree, but how does this apply to a list? Do I misunderstand the text, since English isn't my native language?
[1]http://msdn.microsoft.com/en-us/library/ms379571.aspx
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
这适用于任何可随机访问的容器。对于列表，您将首先转到中间元素。假设这不是目标，排序会告诉您目标是位于上部子列表还是下部子列表中。这本质上变成了二分搜索，与通过 B 树搜索没有什么不同。
This works for any container that is randomly accessible. In the case of a list you would go to the middle element first. Assuming that's not the target, the ordering tells you if the target will be in the upper sublist or the lower sublist. This essentially turns into a binary search, no different than searching through a b-tree.
二分查找，检查中间，如果目标较高，则必须位于右侧，如果较小，则位于中间，依此类推。每次将列表一分为二时，时间复杂度为 O(log n)
Binary search, check middle if target is higher it must reside in the right side, if less its the middle number and so on. Each time you divide the list in two which leaves you with O(log n)