[問題] 98 交大資訊 線代&資結

[lh132 (lh132)]

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
→ ssccg:1 false
→ ssccg:2(a) 我覺得是true，heapsort也是每輪選一個極值，只是選法
→ ssccg:是O(logn)，而selection是O(n)  (c)in-place就是space為O(1)
→ ssccg:3. T(n) = T(n-1) + logn
→ ssccg: ↑ 這是只有後面部分，整個heapsort是O(n)+T(n)
→ ssccg:1.題目的寫法是 T = 由B到標準基底的矩陣表示法
→ ssccg:則[u]B是否等於 (T^t)u，因為[u]B = (T^-1)u
→ ssccg:所以要B為orthonormal basis才對
推 ericland:還好還好 我第一題跟樓上想法一樣 緊張一下!
推 sHackG:s大應該穩上了 很強
→ lh132:了解了~謝謝，我猜S大有機會挑戰台大榜首XD