algorithm - Stack-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)准确地说，假设 insert 是Theta(logn)。

i步骤成本c1 + c2*log(i)（的c1常数pop()是c2AVL 插入保证的常数），因此您得到：

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)- 因此这是您的总复杂性。