将N个元素添加到空AVL树中的运行时间 [英] Running time of adding N elements into an empty AVL tree

问题描述

高度为h的avl树的最小节点"的公式是递归的:n(0)= 1，n(1)= 2n(h)= 1 + n(h-1)+ n(h-2)

The formula for "minimum nodes for an avl tree in height h" is recursive: n(0)=1, n(1)=2 n(h)= 1+n(h-1)+n(h-2)

另一方面，我在互联网上发现这是为了解释向空avl树添加N个元素的复杂性:

On the other hand, i found this in the internet for explanation of the complexity of adding N elements to a empty avl tree:

Well, imagine the tree being built.
One by one, the elements go through the tree nodes, and chose their abode by          taking either a left or a right. The tree balances itself every time the heights   are too skewed.

Of course, the cost of balancing the tree is an O(1) operation, so I do not consider that in the complexity analysis.

Complexity: log(1)+log(2)+log(3)+....+log(n)
=log(n!)
=O(nlogn-n+O(log(n)))
=O(nlogn)

但是这是我不明白的原因，如果不是每次我添加一个元素时高度都会增加，为什么计算log(n！)是为什么?因为给出的递归公式适用于一个大的N，所以avl高度仅在许多元素之后才增加，所以渐近不应该比log(n！)好吗?

But here is what i do not understand, why is the calculation log(n!) if NOT every time i add an element the height increases? since the recursive formula presented applies that for a big N, the avl height increases only after a lot of elements, so asymptotically shouldn't it be better then log(n!)?

此外，最糟糕的情况是什么?在这种复杂情况下，是否存在更坏的情况和最好的情况?例如，假设我要添加特定的N个元素，不同的运行是否可以有更好的运行时间?还是我可以说从高级位置知道要在其中添加每个元素，因此运行时间会很紧?

Also, what is the worse case for this? Is there a worse case and best case in this situation of complexity? For example, assume i have specific N elements i am adding, could there be a better running time for different runs? Or can i say it is known from advanced where each element is going to be added so the running time is bounded tight?

推荐答案

简单的上界解释

如果您有n个元素，则一次插入最多将花费log(n)时间.如果我们假设这是所有n个项目的最坏情况插入时间，那么您得到的 O(n * log(n))无需复杂的解释.

If you have n elements, the most time one insert will take is log(n) time. If we assume this worse case insert time for all n items, then you get O(n*log(n)) without the complex explanation.

另一种查看方式是:

log(1)+ log(2)+ log(3)+ ... + log(n)<n * log(n)= log(n)+ log(n)+ ... + log(n)

log(1) + log(2) + log(3) + ... + log(n) < n*log(n) = log(n) + log(n) + ... + log(n)

这篇关于将N个元素添加到空AVL树中的运行时间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！