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