1
假裝我有一個算法從堆棧中彈出每個元素並將它們插入到AVL樹中。Stack-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)?
爲什麼?
假裝我有一個算法從堆棧中彈出每個元素並將它們插入到AVL樹中。Stack-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)?
爲什麼?
你的算法是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)
- 因此這是你的總體複雜性。