Re: [理工] 102 台大電機丙 資結 對答案
※ 引述《PTT007 (鍵盤007)》之銘言：
: 請問第3題要怎麼算？
: 還有第2題和第23題正確的複雜度應該是多少？
: 謝謝~
→
,
一併回答
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!)
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
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 1.161.163.229
→
02/24 08:54, , 1F
02/24 08:54, 1F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 9 之 18 篇)：