问不同数据结构的大O运行时间

EN

我假设您需要插入所有元素的总时间：

(1)对于AVL树，在最佳情况下，永远不需要在根以下，即所有元素都等于根，因此它将是O(n)。不需要再加深超过一步，不管树的大小。每个元素O(1)。

(2) 树的最坏情况:向树插入n个整数是O(nlogn)。每一步都是O(log(T))，其中T是该时刻的大小。O(log1) + O (log2) + ... + O(logn) = O(log1 + log2 + ... + logn) = O(log(1*...*n)) = O(nlogn)。因此，O(nlogn).O(logn)每一个元素

(3) no结构强制，最佳情况，仍然O(n)，同样的理由(1)。在最好的情况下，您添加的所有元素都是根，因此您永远不需要在树中下降，不管它的大小如何。每个元素O(1)。

(4)对于no结构强制，最坏情况：正如在其他答案中所说的，找到每个元素的位置是O(n)，所以总的来说，O(n^2)的复杂度将是最坏的。每个元素O(n)。

是的，你是对的，如果你用n乘以所有的东西，你的运行时间是一个元素。

插入n整数如何导致O(logn)的大O。这没有任何意义。当然，读取整数本身至少需要O(n)。

因此，对于不平衡的BST示例，最坏的情况是插入一个排序的数字列表(如1,2,3,4 )。插入1需要0的时间。插入2需要~1时间。插入3需要~2时间。等等，这相当于1+2+3+...+n = O(n^2)。

同样，在最好的情况下，每次后续插入都需要log(i)时间。所以总运行时间是log(1)+log(2)+log(3)+...+log(n)。这一评估结果并不是立即显而易见的。但是，如果你知道一些微积分，你可以看到，这是(几乎)梯形规则逼近的积分，从1到n，这大约是nlogn - n = O(nlogn)。

我相信你可以对AVL树做类似的分析。