想问以下资结数题 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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1578046757.A.07C.html