作者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