Research Space for Linear Algebra & Discrete Mathematics
1.n!個leaf 用decision tree 判斷其高度為logn!=nlogn這比較像是資結的....2.拍謝 看巄摩@@3.我會用 (1+x)^n直接微耶 不過一題10分 看你囉4.等價關係就是整數分割我是直接拆平方數相加但是題庫班老師有寫證明大概想法是A=A1 U A2 U A3...|A1|=n1 |A2|=n2 |A3|=n3...等價關係為n=n1+n2+n3+...r=n1^2+n^2+n^3+...r-n=n1(n1-1)+n2(n2-1)....=>r-n為偶數所以如有等價關係r-n為偶數是必要條件20-7就不考慮但是就算是偶數還是要找看看有沒有的20=16+1+1+1+1 //4+1+1+1=7元素31=25+4+1+1 //5+2+1+1=9元素 失敗
4.(b) 就是證明sort的方法數最少就是omega(nlogn)吧Problem2 二項式展開整理應該就可以了3.我想到的是用個數去解釋不可能(a)扣掉反身性的7個 剩下的應該要對稱 所以減7後的個數應該是偶數 所以a不可能(b)7個反身性的加上(1,2)(2,1)(3,4)(4,3)就滿足r=11了(c)還在想...這是我的一點想法~
1. 這是個很重要的定理, 老師上課時應該有稍微提一下, 對於comparison based的sorting algorithm來說, 要排 n 個 items, 其時間複雜度的lowerbound為Ω(nlogn), 證明大置上的觀念是, 考慮有n!個leaves的decision tree, 因為最佳狀況的decision tree是長成full binary tree的樣子, 此時的樹高為 Ɵ(log(n!)) = Ɵ(nlogn)2. 這題是第12章的範圍, 要會這題可能要稍為讀一下那一章, 答案是24. 第一個r=20用關係矩陣想就知道辦不到, 因為扣掉對角線全部要是1然後矩陣又要對稱, 20-7=13為奇數辦不到, 其它的就如前面同學所說老師在題庫班教的方法, 假設現有 i 個等價類, 令 ni 為第 i 個等價類裡面的元素個數, 因為每個等價類中都會有 ni^2 個關係, 所以(1) n1+...+n7 = 7(2) (n1)^2 + ... + (n7)^2 = r從 1 開始的將平方數列出如下:1 2 3 4 5 61 4 9 16 25 36則可觀察出因為 11 = 3*1 + 2*4,所以 r=11 OK就隨便定義出一個等價類個數分別是1, 1, 1, 2, 2 的關係即可, 例如[1], [2], [3], [4]=[5], [6]=[7]r=31藉由類似的討論方式可知辦不到
張貼留言
3 則留言:
1.
n!個leaf 用decision tree 判斷
其高度為logn!=nlogn
這比較像是資結的....
2.拍謝 看巄摩@@
3.我會用 (1+x)^n直接微耶
不過一題10分 看你囉
4.
等價關係就是整數分割
我是直接拆平方數相加
但是題庫班老師有寫證明
大概想法是
A=A1 U A2 U A3...
|A1|=n1 |A2|=n2 |A3|=n3...
等價關係為
n=n1+n2+n3+...
r=n1^2+n^2+n^3+...
r-n=n1(n1-1)+n2(n2-1)....
=>r-n為偶數
所以如有等價關係r-n為偶數是必要條件
20-7就不考慮
但是就算是偶數還是要找看看有沒有的
20=16+1+1+1+1 //4+1+1+1=7元素
31=25+4+1+1 //5+2+1+1=9元素 失敗
4.(b) 就是證明sort的方法數最少就是omega(nlogn)吧
Problem2 二項式展開整理應該就可以了
3.我想到的是用個數去解釋不可能
(a)扣掉反身性的7個 剩下的應該要對稱 所以減7後的個數應該是偶數 所以a不可能
(b)7個反身性的加上(1,2)(2,1)(3,4)(4,3)就滿足r=11了
(c)還在想...
這是我的一點想法~
1. 這是個很重要的定理, 老師上課時應該有稍微提一下, 對於comparison based的sorting algorithm來說, 要排 n 個 items, 其時間複雜度的lowerbound為Ω(nlogn), 證明大置上的觀念是, 考慮有n!個leaves的decision tree, 因為最佳狀況的decision tree是長成full binary tree的樣子, 此時的樹高為 Ɵ(log(n!)) = Ɵ(nlogn)
2. 這題是第12章的範圍, 要會這題可能要稍為讀一下那一章, 答案是2
4. 第一個r=20用關係矩陣想就知道辦不到, 因為扣掉對角線全部要是1然後矩陣又要對稱, 20-7=13為奇數辦不到, 其它的就如前面同學所說老師在題庫班教的方法, 假設現有 i 個等價類, 令 ni 為第 i 個等價類裡面的元素個數, 因為每個等價類中都會有 ni^2 個關係, 所以
(1) n1+...+n7 = 7
(2) (n1)^2 + ... + (n7)^2 = r
從 1 開始的將平方數列出如下:
1 2 3 4 5 6
1 4 9 16 25 36
則可觀察出因為 11 = 3*1 + 2*4,
所以 r=11 OK
就隨便定義出一個等價類個數分別是
1, 1, 1, 2, 2 的關係即可, 例如
[1], [2], [3], [4]=[5], [6]=[7]
r=31藉由類似的討論方式可知辦不到
張貼留言