将 n 个值添加到空链表以便对其进行排序的时间复杂度?

Question

我有n 个未排序的值作为输入，还有一个空的链表。

这些n个值以这样一种方式添加到列表中，即在列表结束时对列表进行排序。

在最坏的情况下，最有效的算法的时间复杂度是多少？

Answer 1

通常链表只能通过其头部访问;没有对任何节点的随机访问。这排除了对二进制搜索的任何使用。

因此，每当需要将新值添加到链表中时，起点始终是列表的头部。继续操作的唯一方法是跟随下一个指针指向列表中的下一个节点，直到找到一个好的插入点，可以在其中插入新节点。

在伪代码中：

insert_value_in_list(head, value):
# create a node for the value
node = new Node(value)
# find out where it should be injected in the list
prev = NIL
node = head
while node is not NIL and node.value < value:
prev = node
node = node.next
# if there is a node that should precede...
if prev is not NIL:
node.next = prev.next
prev.next = node
else: # if there is no node that should precede, then make it the new head
node.next = head
head = node
return head

此算法中的循环可以进行 n次迭代，其中n是列表的当前长度。当插入的值大于列表中已有的所有值时，会发生这种最坏的情况。

因此，当像这样插入n个值时，该循环的迭代次数可能是最坏的情况：

0 + 1 + 2 + 3 + 4 + 5 + ... + n-1

这等于 (n-1(n/2，即O(n²(。当插入的值按其排序顺序插入时，会发生最坏的情况。

插入算法的所有其他部分都在恒定时间内运行，因此最坏情况下的时间复杂度为(On²(。

请注意，当输入与排序顺序相反时，最佳情况会发生。在这种情况下，所有值都可以附加到列表中，并且此类预置操作在常量时间内运行。那么整体时间复杂度是O(n(- 最佳情况。