在排序的单个和双向链表中插入和搜索的平均和最差运行时间是O（1）和O（n）。在最好的情况下，运行时的复杂性是否相同？
换句话说，在最好的情况下，排序的单一和双向链表是否有O（1）时间插入和O（n）时间搜索？
想想这样：
在最好的情况下，当你搜索时，你看到的第一个元素就是你想要的元素，所以你已经完成了（实际上是很多搜索算法的情况）。这与链表的长度无关，即无论链表有多长，它都需要相同的时间，因此它是O(1)。
在最佳情况下，特定元素之后的插入是相同的：您在特定元素之后插入，这又与列表的长度无关，因此它是O(1)。
我应该注意到，在最好的情况下运行时复杂性不是很有趣，因为在最好的情况下，一切都通常很快。人们通常只谈论平均案例运行时间，因为接近平均情况会经常发生，最糟糕的是因为你想知道你的算法有时会真的非常糟糕。