Ref 上插入排序的时间复杂度。基于链表？
Time Complexity for Insertion Sort on Ref. Based Linked-List?
这里是实际问题：
"what is the time complexity if the insertion sort is done on a reference-based linked list?"
我想应该是 O(1)，对吧？因为您将检查节点，直到找到 PREVIOUS 和 AFTER 节点，设置指针，就可以了。因此，并不是每个节点都需要检查，所以它不能是 O(n)。
大O表示法一般指的是最坏情况下的复杂度。
插入一个已经排序的列表（我认为这是你根据最后一段理解问题的方式）的复杂度为 O(n)，因为最坏的情况是插入一个元素列表末尾，意味着有 n 次迭代。
对未排序的链表执行插入排序需要将 n 个元素插入链表，复杂度为 O(n^2)。
这里是实际问题：
"what is the time complexity if the insertion sort is done on a reference-based linked list?"
我想应该是 O(1)，对吧？因为您将检查节点，直到找到 PREVIOUS 和 AFTER 节点，设置指针，就可以了。因此，并不是每个节点都需要检查，所以它不能是 O(n)。
大O表示法一般指的是最坏情况下的复杂度。
插入一个已经排序的列表（我认为这是你根据最后一段理解问题的方式）的复杂度为 O(n)，因为最坏的情况是插入一个元素列表末尾，意味着有 n 次迭代。
对未排序的链表执行插入排序需要将 n 个元素插入链表，复杂度为 O(n^2)。