栈- avl传输算法

Question

假设我有一个算法，可以从堆栈中弹出每个元素并将它们插入到AVL树中。

If pop () is a O (1) method and insert () is an O(log n) method,  
my algorithm is O(log n), O (n) or O(n log n)?

为什么?

Answer 1

你的算法是O(nlogn)，或Theta(nlogn)确切地说，假设插入是Theta(logn)

i步耗费c1 + c2*log(i) (c1是pop()的常数，c2是AVL插入保证的常数)，所以你得到:

c1 + c2*log(1) + c1 + c2*log(2) + .... + c1 + c2*log(n) = 
= c1*n + c2*log(1*2*...*n) = c1*n + c2*log(n!) <= (for large enough n) (c2+1)*log(n!)

如果我们"忽略"这些常量，它的可读性会好得多(当然不太准确，必须小心处理，但这对直觉很好):

log(1) + log(2) + ... + log(n) = log(1*2*...*n) = log(n!)
and log(n!) is in O(nlogn)

已知log(n!)在Theta(nlogn)中-因此这是您的总复杂度。