Re: [理工] [DS]100台大電機丙 多選第十題
看板Grad-ProbAsk作者jimmylin1024 (shibaLover)時間5年前 (2020/11/22 09:23)推噓0(0推 0噓 0→)留言0則, 0人參與討論串2/2 (看更多)
※ 引述《Billgaspeed (Billgaspeed)》之銘言：
: (A)The number of rotations per insert/delete operation in a
: Red-Black tree is O(log n)
: 想問這個選項哪裡錯誤阿?
: 不是根據他的高度 log n 決定的嗎?
: 而且Red Black Tree 沒有skewed tree 的問題吧?
: 還是我疏漏啥了QQ
想請問如果題目給的bound 不是tight bound還算是正確的嗎？
以這題來說就是rotation 的次數是O(1)，但是根據定義説它是O(logn)也不算錯，那考試的時候這種選項要選嗎？
-----
Sent from JPTT on my iPhone
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.136.28.218 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1606008215.A.BB1.html
討論串 (同標題文章)
完整討論串 (本文為第 2 之 2 篇)：