作者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
1F:推 timrau:怎样"balance"结果差很多, 不然资料结构的书怎麽会那麽厚.. 12/04 22:02
2F:→ timrau:不同方法 code长度、工程大小差异很大 12/04 22:04
3F:推 ric2k1:本次作业不用做 balance <== 大工程 12/04 22:58
4F:→ ric2k1:如果是 random input sequence 的话,有没有 balance 在 12/04 22:59
5F:→ ric2k1:测资没有很大的时候其实不会差很多,当然,worst case 是 12/04 23:00
6F:→ ric2k1:差很多。你也可以跟 STL 的 "set" 比较看看。 12/04 23:01
7F:推 aitjcize:red black tree XDD 12/05 10:15
8F:推 johnjohnlin:楼上不要再提那个悲剧了XDDDD 12/05 11:11
9F:推 ric2k1:有八卦!! 12/05 12:31
10F:推 TommyKSHS:红黑树 XDD 12/05 14:15
11F:推 hiroki1139:红黑树有梗吗?? 12/06 00:47
12F:推 hihisasa:是乱伦的悲剧吗?? 猜的 哈 12/06 00:59
13F:推 ji394vul3m6:应该只是想到上学期的演算法吧XDD 12/06 11:56
14F:→ ckmarkoh:所以是啥悲剧? 12/07 22:38