作者lh132 (lh132)
看板Grad-ProbAsk
標題[問題] 98 交大資訊 線代&資結
時間Thu Mar 19 20:08:05 2009
1.線代選擇題第六題的(c)為true嗎?題目如下
If B={v1,v2,...,vn} is an ordered basis of V, then for any vector u belongs V,
the coordinate of u can be given by [u]B=[<u1,v1> <u2,v2> ... <un,vn>]^T.
2.DS的選擇題第13題
(a)heap sort可視為selection sort的改良
(c)the sorting algorithmm is in-place
這兩個為true嗎?如果是，想請問in-place的意思是?
3.Heap sort若要以遞迴式子表示time complexity，該如何表示?
麻煩大家指點了，謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 163.18.99.201
1F：→ ssccg:1 false 03/19 20:22
2F：→ ssccg:2(a) 我覺得是true，heapsort也是每輪選一個極值，只是選法 03/19 20:25
3F：→ ssccg:是O(logn)，而selection是O(n) (c)in-place就是space為O(1) 03/19 20:26
4F：→ ssccg:3. T(n) = T(n-1) + logn 03/19 20:26
5F：→ ssccg: ↑ 這是只有後面部分，整個heapsort是O(n)+T(n) 03/19 20:27
6F：→ ssccg:1.題目的寫法是 T = 由B到標準基底的矩陣表示法 03/19 20:34
7F：→ ssccg:則[u]B是否等於 (T^t)u，因為[u]B = (T^-1)u 03/19 20:35
8F：→ ssccg:所以要B為orthonormal basis才對 03/19 20:35
9F：推 ericland:還好還好 我第一題跟樓上想法一樣 緊張一下! 03/19 21:06
10F：推 sHackG:s大應該穩上了 很強 03/19 21:15
11F：→ lh132:了解了~謝謝，我猜S大有機會挑戰台大榜首XD 03/20 09:51