※ 引述《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