作者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