推 jeremyyuan: 4 我也寫false median用augmented AVL不是可以到logn12/24 16:36
→ jeremyyuan: 嗎 甚至直接用一個指標指 1by1給不就O(1)? 16E應該錯12/24 16:36
→ jeremyyuan: 的 splay會斜取 19我也有選a12/24 16:36
splay分攤時間應該是logn？ 洪逸的筆記這樣寫的
※ 編輯: mistel (114.136.184.208 臺灣), 12/24/2019 16:54:30
→ mistel: 不過真要說heap的delete也可以分攤到O(1)，所以有時候真 12/24 16:55
→ mistel: 不知道台大到底該答什麼... 12/24 16:55
→ jeremyyuan: worst case是O(n) 12/24 16:56
→ mistel: 我看到了 感謝你 12/24 16:58
→ jeremyyuan: 沒事 worst case也要用amortized 是我錯了 12/24 17:01
→ jeremyyuan: 不過感覺怪怪的 worst是O(n)然後又amortized ... 12/24 17:15
→ mistel: 我看其他網站寫O(n) worst case，不知道聖經本寫什麼：（ 12/25 12:14
→ jeremyyuan: 我看題庫班 洪逸也是寫ABCD worst case 還是O(n)啦 12/25 12:43
→ jeremyyuan: 但維基把他amortized了= = 12/25 12:43