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

Question

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

那些n值以这样的方式添加到列表中，以便最后对列表进行排序。

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

Answer 1

通常，仅通过链表的head访问链表；没有随机访问任何节点。这不包括对二进制搜索的任何使用。

因此，每当需要将新值添加到链接列表时，起点始终是列表的开头。唯一的进行方法是跟随next指针指向列表中的下一个节点，直到找到一个好的插入点为止，可以在其中插入新节点。

使用伪代码：

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²）

。]

注意，best

情况发生在输入与排序顺序相反的情况下。在那种情况下，所有值都可以放在列表的前面，并且这样的前置操作会在恒定时间内运行。那么总的时间复杂度是O（n）-最佳情况。