c-链表的时间复杂度是多少

Question

假设您希望在保持排序顺序的同时将n个元素插入到一个空链表中。最坏的情况是什么时候？

Answer 1

如果，通过"保持排序顺序"；，你的意思是它们已经排序了，这是一个O(n)操作，因为你只需将它们中的每一个都钉在列表的末尾(你可以记录当前的末尾，而不是每次都搜索它(：

make new list from first value, keeping pointer to last, O(1)
for curr in second and subsequent values, O(n):
add to list using last, update last, O(1)

如果你的意思是它们不是排序的，但应该是，那就是O(n2)，因为每个的n新值将导致O(n)搜索，然后是O(1)插入：

for curr in values, O(n):
find insertion point, O(n)
insert at that point, O(1)

Answer 2

如果在每次新插入元素后进行排序，那么最坏情况下的时间复杂度将为o(n^2(。(插入需要o(1(，然后排序需要o(n^2(。(

或者，如果一次插入所有元素，然后应用排序，则需要o(nlogn(。(带合并排序(