链表的最佳搜索算法
The Best Search Algorithm for a Linked List
我必须尽可能高效地编写一个程序，将给定节点插入到已排序的链表中。我在想二进制搜索在平均和最坏情况下如何比线性搜索更快，但是当我用谷歌搜索时，运行时间是 O(nlogn)？我应该在单链表上进行线性搜索还是在双链表上进行二分搜索，为什么那个（要选择的）更快？
另外，双向链表的二分查找算法 > O(logn) 怎么样？
（没有人推荐 SkipList，我认为他们违反了规则，因为我们有另一个严格针对该数据结构的实现）
所以基本上对 LL 进行二分搜索是 O(n log n)，因为您需要遍历列表 n 次以搜索项目，然后记录 n 次以拆分搜索集。但这只有在每次都从头遍历 LL 时才成立。
理想情况下，如果你想出某种方法（这是可能的！）从其他地方开始，比如...搜索集的中间，那么你就不需要总是遍历列表 n 次来开始搜索并且可以将您的算法优化为 O(log n)。
二进制搜索在数组上非常快，因为它非常快速和简单地访问数组中任意两个给定元素索引之间的中间索引。这使得 运行 宁时间复杂度为 O(log n) 而取常数 O(1) space.
对于链表来说就不同了，因为为了访问中间的元素，我们需要一个节点一个节点的遍历，因此找到中间节点可以运行复杂度为O(n)
因此二分查找在链表上慢而在数组上快
你有两个选择。
- 线性搜索无序列表。这是 O(N)。
- 线性搜索有序列表。这也是 O(N)，但速度是原来的两倍，因为平均而言，您搜索的项目会在中间，如果找不到，您可以停在那里。
您不能选择二进制搜索，因为您不能直接访问链表的元素。
但是如果你认为搜索是决定速率的步骤，你根本不应该使用链表：你应该使用排序数组、堆、树等
可以使用跳表进行二分搜索。如果您同时设置 skip 2, 4, 8, ..., 2^n ，您将花费指针数是链表的两倍。然后每次搜索都可以得到 O(log n)。
如果您在每个节点中的数据存储都非常大，应用它会非常有效。
上阅读更多内容
我必须尽可能高效地编写一个程序，将给定节点插入到已排序的链表中。我在想二进制搜索在平均和最坏情况下如何比线性搜索更快，但是当我用谷歌搜索时，运行时间是 O(nlogn)？我应该在单链表上进行线性搜索还是在双链表上进行二分搜索，为什么那个（要选择的）更快？
另外，双向链表的二分查找算法 > O(logn) 怎么样？ （没有人推荐 SkipList，我认为他们违反了规则，因为我们有另一个严格针对该数据结构的实现）
所以基本上对 LL 进行二分搜索是 O(n log n)，因为您需要遍历列表 n 次以搜索项目，然后记录 n 次以拆分搜索集。但这只有在每次都从头遍历 LL 时才成立。
理想情况下，如果你想出某种方法（这是可能的！）从其他地方开始，比如...搜索集的中间，那么你就不需要总是遍历列表 n 次来开始搜索并且可以将您的算法优化为 O(log n)。
二进制搜索在数组上非常快，因为它非常快速和简单地访问数组中任意两个给定元素索引之间的中间索引。这使得 运行 宁时间复杂度为 O(log n) 而取常数 O(1) space.
对于链表来说就不同了，因为为了访问中间的元素，我们需要一个节点一个节点的遍历，因此找到中间节点可以运行复杂度为O(n)
因此二分查找在链表上慢而在数组上快
你有两个选择。
- 线性搜索无序列表。这是 O(N)。
- 线性搜索有序列表。这也是 O(N)，但速度是原来的两倍，因为平均而言，您搜索的项目会在中间，如果找不到，您可以停在那里。
您不能选择二进制搜索，因为您不能直接访问链表的元素。
但是如果你认为搜索是决定速率的步骤，你根本不应该使用链表：你应该使用排序数组、堆、树等
可以使用跳表进行二分搜索。如果您同时设置 skip 2, 4, 8, ..., 2^n ，您将花费指针数是链表的两倍。然后每次搜索都可以得到 O(log n)。
如果您在每个节点中的数据存储都非常大，应用它会非常有效。
上阅读更多内容