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