基于Ref的链表上插入排序的时间复杂度

Question

实际问题是:

"如果在基于引用的链表上进行插入排序，时间复杂度是多少?"

我认为它应该是O(1)，对吗?因为您将检查节点，直到找到PREVIOUS，以及应该是AFTER的节点，所以设置指针，这样就可以了。因此，不是每个节点都需要检查，所以它不能是O(n)。

Answer 1

大0符号通常指的是最坏情况下的复杂度。

插入一个已经排序的列表(我认为这是你基于最后一段理解问题的方式)将具有O(n)的复杂性，因为最坏的情况是插入一个元素在列表的末尾，这意味着有n次迭代。

在未排序的链表上执行插入排序需要在链表中插入n个元素，复杂度为O(n^2)。