[理工] 資演數題 advanced tree
想問以下資結數題
https://i.imgur.com/nzxdF6e.jpg
21 22，想問關於splay tree 的splay operation跟delete operation的時間複雜度
演算法的課本提到splay tree operation的amortized cost是O(lgn) 但網路上的筆記寫調整最差的過程是O(n) , 然後21題問的是worst case想確認這兩題答案
23，紅黑樹,如果一條path經過三個紅點,那這顆樹至少會有多少個黑點？該怎麼畫呢？
25 26 binomial heap
25從一個unordered array建heap的時間複雜度？我的想法是Insert O(lgn) 做n次insert建立O(nlgn)?
26 原本想法是2019/32的商 但畫出來好像不太對
27 30 fibonacci heap
27 課本寫n個node的fibonacci heap 任一點的degree會小於等於 n取log以golden ratio為底 所以最大degree是D?
30 沒有想法
31 32 disjoint-set
想問這題要寫AA還是BB比較好 課本寫的worst case時間複雜度是O(m a(n)) , a(n)在可以想到的情況是小於等於4的
謝謝
-----
Sent from JPTT on my iPhone
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.140.163.132 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1578046757.A.07C.html
推
01/03 21:58,
6年前
, 1F
01/03 21:58, 1F
→
01/03 21:59,
6年前
, 2F
01/03 21:59, 2F