作者ckmarkoh (阿傑)
看板EE_DSnP
標題Re: [問題] HW5的評分
時間Sat Dec 4 21:42:29 2010
※ 引述《ckmarkoh (阿傑)》之銘言：
: Grading ---
: Correctness and efficiency of your programs (350 pts)
: Performance study report “adtComp.pdf” (100 pts).
: 請問
: 如果三個程式的Correctness 都可以達到100%
: 但是efficiency很差
: 那大概可以拿到350pts中的多少?
: 也就是說 Correctness和efficiency各占多少比例?
昨天測試完了bst後 看講義才發現
好像下次上課才會講到要怎樣把tree做balance
如果bst沒有balance的功能 用random的string去測它
和有balance功能的比起來 performance的差異應該不大
但如果是依序輸入一個已經sort好的序列 到沒有balance功能的tree
那它存出來的形狀就和dlist沒甚麼兩樣 performance亦會如此
而且還會多一個pointer(如果有parent pointer的話...)
不知道要修改已經寫好的code 會不會是個很大的工程...
也不知道助教會怎麼測..
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 58.114.204.36
推 timrau:怎樣"balance"結果差很多, 不然資料結構的書怎麼會那麼厚.. 12/04 22:02
→ timrau:不同方法 code長度、工程大小差異很大 12/04 22:04
推 ric2k1:本次作業不用做 balance <== 大工程 12/04 22:58
→ ric2k1:如果是 random input sequence 的話，有沒有 balance 在 12/04 22:59
→ ric2k1:測資沒有很大的時候其實不會差很多，當然，worst case 是 12/04 23:00
→ ric2k1:差很多。你也可以跟 STL 的 "set" 比較看看。 12/04 23:01
推 aitjcize:red black tree XDD 12/05 10:15
推 johnjohnlin:樓上不要再提那個悲劇了XDDDD 12/05 11:11
推 ric2k1:有八卦!! 12/05 12:31
推 TommyKSHS:紅黑樹 XDD 12/05 14:15
推 hiroki1139:紅黑樹有梗嗎?? 12/06 00:47
推 hihisasa:是亂倫的悲劇嗎？？ 猜的 哈 12/06 00:59
推 ji394vul3m6:應該只是想到上學期的演算法吧XDD 12/06 11:56
→ ckmarkoh:所以是啥悲劇? 12/07 22:38