作者Ultor (m(_ _)m)
看板EE_DSnP
標題[問題] size
時間Sat May 9 23:21:53 2009
這次作業 bst 和 dlist 的 size()
是要用 linear time 的 size() 呢
還是可以偷偷存一個 _size
然後 就可以用 constant time 的 size() 呢?
謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 124.11.209.16
1F：推 ric2k1:原則上是不要, 不過你也可是試試看啊, 看看 maintian _size 05/09 23:49
2F：→ ric2k1:的 effort 與 需要時再算一遍的 cpu time 的差別 05/09 23:50
3F：推 timrau:沒有splice operation的狀況下應該是相當便宜... 05/10 00:01
4F：推 ric2k1:那就要看你使用 ADT 時到底 push / pop 的次數多, 還是呼叫 05/10 00:10
5F：→ ric2k1:size() 的次數多, 因為 push/pop 也是要去 maintain _size, 05/10 00:11
6F：→ ric2k1:而像是 for (li = ...; li++), 其實是不用到 _size 的, 05/10 00:12
7F：→ ric2k1:amortize 起來我覺得有 _size 其實也不會比較好... 05/10 00:13
8F：→ ric2k1:不過歡迎試試看, 然後在 report 講一下你的觀察心得 05/10 00:13
9F：推 bnsblue:去年好像也討論過這個問題... 05/10 16:35