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) - 因此這是你的總體複雜性。