Re: [理工] 102 台大電機丙 資結 對答案
作者: koala0716 2016-10-26 20:37:12
※ 引述《cocoyan (摳摳厭)》之銘言：
: ※ 引述《PTT007 (鍵盤007)》之銘言：
: : 請問第3題要怎麼算？
: : 還有第2題和第23題正確的複雜度應該是多少？
: : 謝謝~
: → PTT007:請問第7題的反例怎麼取？
: 一併回答
: 2.B
: double linked list 在每個node有兩個pointer
: 所以加上data後空間使用為3n=Θ(n)
: 3.A
: 這題用猜的啊XD
: 看到swap(a[k],a[i]);
: permuteGen(a,k+1,n);
: swqp(a[k],a[i]);
: 後就應該要猜到是做出所有排列Θ(n!)
: 而cout<<a[i]<<" ";就把每個排列(n-character)印出來Θ(n)
: T(n)=Θ(n)*Θ(n!)=Θ(n*n!)
雖然有點久了 但是還是想弱弱的討論一下 這題else的for少一次，排列變成(n-1)!
乘上印出的n後為 n! 與原本的n*n!有差耶! 這樣答案是不是要改成false啊?
還是Θ這樣沒差呢???
: 7.B
: 下圖是個100-ary tree
: O
: /
: O
: n=2,k=100,|E|=1,n-k+1=-97≠1
: 23.F
: 用DFSＯ或BFS就可以
: 所以複雜度為Ｏ(|V|+|E|)=Ｏ(n+(n^2-n)/2)=Ｏ(n^2),此為最差情況|E|=(n^2-n)/2
: 最好情況為Ｏ(n),|E|=n-1
: ※ 引述《PTT007 (鍵盤007)》之銘言：
: : 請問第3題要怎麼算？
: : 還有第2題和第23題正確的複雜度應該是多少？
: : 謝謝~
: → PTT007:請問第7題的反例怎麼取？
: 一併回答
: 2.B
: double linked list 在每個node有兩個pointer
: 所以加上data後空間使用為3n=Θ(n)
: 3.A
: 這題用猜的啊XD
: 看到swap(a[k],a[i]);
: permuteGen(a,k+1,n);
: swqp(a[k],a[i]);
: 後就應該要猜到是做出所有排列Θ(n!)
: 而cout<<a[i]<<" ";就把每個排列(n-character)印出來Θ(n)
: T(n)=Θ(n)*Θ(n!)=Θ(n*n!)
雖然有點久了 但是還是想弱弱的討論一下 這題else的for少一次，排列變成(n-1)!
乘上印出的n後為 n! 與原本的n*n!有差耶! 這樣答案是不是要改成false啊?
還是Θ這樣沒差呢???
: 7.B
: 下圖是個100-ary tree
: O
: /
: O
: n=2,k=100,|E|=1,n-k+1=-97≠1
: 23.F
: 用DFSＯ或BFS就可以
: 所以複雜度為Ｏ(|V|+|E|)=Ｏ(n+(n^2-n)/2)=Ｏ(n^2),此為最差情況|E|=(n^2-n)/2
: 最好情況為Ｏ(n),|E|=n-1
作者: ken52011219 (呱) 2016-10-26 21:45:00
" target="_blank" rel="nofollow"> 嘗試寫寫看 有誤幫忙更正謝謝作者: active716 (gee jun) 2016-10-26 22:23:00
good
作者: koala0716 2016-10-26 22:46:00
感謝 但底下部分有點看不太懂 不過我是直接用程式跑的