以大 O 表示法插入排序链接列表的复杂性是多少？
以大 O 表示法插入排序链接列表的复杂性是多少？假设我有 5 个元素，插入所有元素的复杂度是多少。
非常感谢
What is the complexity of inserting into sorted link list in big-O notation? Let say I have 5 elements and what is the complexity to insert all of them.
Thank you very much
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
考虑一下对排序链接列表的单个插入意味着什么。您有一个新元素必须位于列表中的某个位置。
1）你必须在列表中找到正确的位置。这是线性搜索。 O(n)
2) 插入很容易：创建新节点，修复指向前一个和下一个节点的指针。 O(1)
在这种情况下，O(n) 超过了 O(1)，所以它是 O(n)。
元素的数量并不真正适用于 big-O，因为它都是基于数量级的。
Think about what a single insertion into a sorted link list means. You have a new element that has to go somewhere in the list.
1) You have to find the right place in the list. This is a linear search. O(n)
2) Insertion is easy: create new node, fix pointers to the previous and next nodes. O(1)
In this case, the O(n) outweighs the O(1) so it's O(n).
The number of elements doesn't really apply to big-O, since it's all based on orders of magnitude.
首先，我建议阅读有关链接列表的维基百科文章，尤其是关于的（小）部分加快搜索速度。
现在，为了回答您的问题，如果您已经知道要插入的位置，则插入链表需要 O(1) 时间。由于我们正在讨论排序链接列表，并且您在不知道元素应该去哪里的情况下插入，因此将花费您 O(n) 时间（因为您必须搜索整个元素）列表来查找元素所在的位置）。请注意，实际添加元素的时间复杂度为 O(1)，就像我上面所说的那样。
请注意，这不是一个非常有效的搜索，因为例如搜索排序数组需要 O(lg(n)) 时间（使用二分搜索）。不幸的是，对于数组，找到元素后，插入本身的时间复杂度不是 O(1)（通常是 O(n)），这意味着使用数组总体上不会加快速度，尽管搜索速度更快。
First, I'd recommend reading the Wikipedia article on Linked Lists, especially the (small) part about speeding up search.
Now, to answer your question, an insertion into a linked list takes O(1) time if you already know where you want to insert it. Since we're talking about a Sorted Linked List, and you're inserting without knowing where an element is supposed to go, it will take you O(n) time (since you have to search the whole list to find the place the element goes). Notice that actually adding the element is O(1), like I said above.
Notice that this is not a very effective search, since searching a sorted array, for example, takes O(lg(n)) time (using a Binary Search). Unfortunately, with an array, after finding the element, the insertion itself is not O(1) (it's usually O(n)), which means that using an array doesn't speed you up overall, even though the search is faster.