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