※ 引述《h04mp6286 (H28)》之銘言：
: 如題,想請問
有些想法 都不知道是否正確 請大家討論QQ
: 1.交大103演算法第10題(switch那題)到底題目意思代表什麼
大概覺得是
把整個看成一個network
則左邊有n/2個開關 右邊也有n/2個
中間兩個大小為n/2的network
得遞迴: S(n) = 2S(n/2) + n
且 S(2) = 1 (輸入為2一個開關就夠)
然後解S(8)
跟S(n)的一般式
: 2.成大演算法第2,3題不太會解有請神人示範解答
第2
我是覺得若M是一個常數的話..
則輸入n很大的時候那個M相對的影響就不大
就把它當成沒有干擾到整個式子(可以這樣嗎)
則時間複雜度
By Master:O(n^4)
第3
半猜半想..
LIS(string s)
先做一個s sorting過後的字串s'(由小到大) //O(nlgn)
cost sequence = Edit Distance(s,s')
cost sequence會有一串對s的操作 //O(n)
叫你刪除的刪除 , 代換的也刪除 , 插入的不要動作
之後把處理過後的s傳出去
end
: 第4題的"X2+X3=8"有什麼特別的意思嗎?
印象中好像constraint graph畫出來有個負環= =..?
這類題目記得跟某個圖論演算法有關 想不起來
: 順便對下DS跟演算法的答案
: 交大103:
: 演算法:(八)a a c b a c a b b c
a d c b ? c a b b c
heap sort 感覺不是divide & conquer..?
: 清大103:
: 演算法:(九)A C
還沒寫...
: 成大103:
: DS:(一)F F F F F
F F F F F
第一題dfs用adj list應該是O(E+V) 雖然說寫O(V^2)理論上也是過..
第二題應該不是唯一
第三題用chaining最差也是O(n)
第四題2e
第五題否
: 演算法:(一)T T F T ?(第5小題看不懂:" w* = min(u,v).... "這串是啥啊)
? F F F ?
第一題不知
第二題一條長鏈在怎麼樣也要O(n)..?因為要從最下面一路向上..?
第三題他們三個都sorting過,
做成一個sorted array也只需O(nlog3) [winner tree]
把sorted array變成balanced bst是線性時間的樣子O(n)
所以最佳時間應該至少也是 nlog3
第四題以下反例
a->b花1 b->c花1 c->d花1
a