[問題] size

[Ultor (m(_ _)m)]

這次作業 bst 和 dlist 的 size()

是要用 linear time 的 size() 呢

還是可以偷偷存一個 _size

然後 就可以用 constant time 的 size() 呢?

謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 124.11.209.16
推 ric2k1:原則上是不要, 不過你也可是試試看啊, 看看 maintian _size
→ ric2k1:的 effort 與 需要時再算一遍的 cpu time 的差別
推 timrau:沒有splice operation的狀況下應該是相當便宜...
推 ric2k1:那就要看你使用 ADT 時到底 push / pop 的次數多, 還是呼叫
→ ric2k1:size() 的次數多, 因為 push/pop 也是要去 maintain _size,
→ ric2k1:而像是 for (li = ...; li++), 其實是不用到 _size 的,
→ ric2k1:amortize 起來我覺得有 _size 其實也不會比較好...
→ ric2k1:不過歡迎試試看, 然後在 report 講一下你的觀察心得
推 bnsblue:去年好像也討論過這個問題...