QA

有序链表插入的时间复杂度是多少？

在有序链表中插入一个元素的时间复杂度通常是 O(n)。这是因为，在有序链表中插入一个元素需要遍历链表，直到找到插入位置。因此，插入的时间复杂度与链表的长度成正比。

在平均情况下，插入一个元素需要遍历链表的一半，因此平均时间复杂度为 O(n)。但是，在最坏情况下，插入元素需要遍历整个链表，此时的时间复杂度为 O(n)。

总的来说，插入操作的时间复杂度为 O(n)，具体取决于链表的长度以及插入元素的位置。