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

看板Grad-ProbAsk作者 (lh132)時間16年前 (2009/03/19 20:08), 編輯推噓2(2推 0噓 9→)
留言11則, 4人參與, 最新討論串1/1
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
→
03/19 20:22, , 1F
1 false
03/19 20:22, 1F
→
03/19 20:25, , 2F
2(a) 我覺得是true，heapsort也是每輪選一個極值，只是選法
03/19 20:25, 2F
→
03/19 20:26, , 3F
是O(logn)，而selection是O(n) (c)in-place就是space為O(1)
03/19 20:26, 3F
→
03/19 20:26, , 4F
3. T(n) = T(n-1) + logn
03/19 20:26, 4F
→
03/19 20:27, , 5F
↑ 這是只有後面部分，整個heapsort是O(n)+T(n)
03/19 20:27, 5F
→
03/19 20:34, , 6F
1.題目的寫法是 T = 由B到標準基底的矩陣表示法
03/19 20:34, 6F
→
03/19 20:35, , 7F
則[u]B是否等於 (T^t)u，因為[u]B = (T^-1)u
03/19 20:35, 7F
→
03/19 20:35, , 8F
所以要B為orthonormal basis才對
03/19 20:35, 8F
推
03/19 21:06, , 9F
還好還好 我第一題跟樓上想法一樣 緊張一下!
03/19 21:06, 9F
推
03/19 21:15, , 10F
s大應該穩上了 很強
03/19 21:15, 10F
→
03/20 09:51, , 11F
了解了~謝謝，我猜S大有機會挑戰台大榜首XD
03/20 09:51, 11F
‣ 更多 lh132 的文章
文章代碼(AID): #19mZMcPh (Grad-ProbAsk)