作者WSzc (WSzc)
看板EE_DSnP
标题[问题] 关於bst跟array的速度
时间Fri May 22 23:32:18 2009
虽然做完了
可是对於bst为什麽do2会慢array这麽多还是有点疑惑耶
在insert的时候bst是比较快
但是到了delete的时候就慢了10倍以上
可是delete的时候(adtd -r xxx)
array花O(n)的时间做memmove的动作
而bst要先找successor
最坏的情况会花O(n)的时间
然後再把这个node换成successor
这个地方应该是constant time吧 只是一堆判断式
(我有加了parent 所以不用花时间trace)
那怎麽会慢这麽多呢(20几秒跟2秒的差距)
还是那些改变pointer指的位置的判断式都会很花时间呢??
谢谢回答!
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 118.161.57.246
1F：推 goodword:我记得老师好像有回答过..... 05/22 23:37
2F：推 Trumen:作业5 random delete的random指的是iterator不是value喔 05/22 23:38
3F：→ goodword:不是delete时慢 是要random找一个来delete时会满久的 05/22 23:38
4F：→ goodword:iterator++ 做random次 才选到要删的那一个 05/22 23:40
5F：→ WSzc:原来如此阿 感谢!! 05/22 23:44