如上
网友回答
时间复杂性分析：T(n)=c+T(k)+T(n-k-1)，此递推式保证算法的时间复杂性为O(n)，也可从递归的角度出发，递归的次数正是结点的个数，而每次递归时间复杂性为常数，所以算法的时间复杂度也为O(n)。
6.8．给出一个使得DKNAP(算法6.7)出现最坏情况的例子，它使得|Si|=2i, 0≤i<n。还要求对n的任意取值都适用。
解：取(P1,P2,…,Pi,…)=(W1,W2,…,Wi,…)=(20,21,…,2i-1,…)
P和W取值相同，使支配原则成立，也就是说不会因为支配原则而删除元素；只要说明不会出现相同元素被删除一个的情形，即可知是最坏的情况。可用归纳法证明此结论。
[附件:]3343.doc
售价：
70金币
如何获得金币？