排序数组、排序链接列表和二进制搜索树在插入、删除的最佳情况下的时间复杂度是多少？

Question

在插入、删除的最佳情况下，排序数组、排序链接列表和二进制搜索树的时间复杂度是多少(以及为什么？)另外，人们通常如何从算法中确定最佳情况。我理解如何从算法中确定更坏的情况，例如，for循环将是O(n)。到目前为止，我只在网上找到了一般的和更糟的案例，没有一个显示出最好的案例。

Answer 1

这取决于你认为什么是最好的情况。例如，如果我认为最好的情况是“插入唯一元素/删除唯一元素”，那么所有的树结构都需要O(1)时间。在这种情况下，我认为没有最好的案例，因为

排序数组中的

1. --链接列表您必须找到插入新元素O(N)的位置，然后必须移动其他元素(数组中的O(n)，链接列表中的O(1) )，在二叉树中删除
2. 的复杂性相同，插入/删除操作需要所有O(h)时间，其中h是树的高度。如果您的树是平衡的(AVL或红黑树)，h= O(log n)，那么复杂性就变成O(log n)

。

在这种情况下，大O表示法描述了所有情况。

一般来说，最好的情况不太被考虑，因为它们已经在中等的情况下被考虑了。