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)，假设插入是 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) 中 - 因此这就是您的总复杂度。