15.
else do A[k]=R[j]
16.
j++
17.
k++
18. while(i<=n1) 19. do A[k++]=L[i++]
6. for j ←1 to n2 7. do R[j] ←A[q+j]
20. while(j<=n2) 21. do A[k++]=R[j++]
8. i ←1
9. j ←1
个递归的解也是Ω(nlgn)。得到解为Θ(nlgn)。
证明：假设当n 1时，T(n) 1是唯一的边界条件， T (n) cn lg n c 1 lg1 0,假设T(n) cn lg n对n / 2成立
T (n) 2T (n / 2) n 2cn / 2lg(n / 2) n
cn lg(n / 2) n cn lg n - (c 1)n cn lg n(当c 1时) 所以，T (n) O(n lg n),下面证T (n) (n lg n)
2
2
22
c n 1 lg( n 1) c n lg( n ) (n)
2
2
22
c n 1 lg(n 1) c n 1 c n lg(n) c n lg 2 (n)
2
2
2
2
cn lg(n 1) c lg(n 1) c n lg(n) c (2n 1) (n)
2
2
2
2
cn lg n c n(lg(n 1) lg n) c lg(n 1) c (2n 1) (n)
再证(n lg n),即要证T (n) cn lg n
设T (n / 2) c(n / 2) lg(n / 2)成立，
则T (n) T (n / 2) T (n / 2) (n)
c(n
/
2)
lg(n
/
2)
c(n
/
2)
lg(n
/
2)
(n)
c
n 2
lg(
n) 2
c
n
2
1
lg(=0,1,...n-1区间上，当q=0或q=n-1时,q2+(n-q-1)2取得最 大值。
• 求导，取极值。 • 或者进行变换
8.2-4在O(1)的时间内，回答出输入的整数中有多少个落在区 间[a...b]内。给出的算法的预处理时间为O(n+k)
• 利用计数排序，由于在计数排序中有一个存储数值个数的临时存储区 C[0...k]，利用这个数组即可
则T (n) T (n / 2) T (n / 2) (n) c(n / 2) lg(n / 2) c(n / 2) lg(n / 2) (
c n 1 lg( n 1) c n lg( n ) (n)
2
2
22
c n 1 lg( n 1) c n lg( n ) (n) cn lg n
第二次作业
• 3.2-3 证明等式lg(n!)=Θ(nlgn)。并证明等式n!=ω(2n)和
n!=o(nn)。
证明：由于(
n
)
n 2
n! nn , 两边取对数可知：lg(n!) (n lg n)
2
3.2-4函数⌈lgn⌉! 是否多项式有界？函数⌈lglgn⌉! 呢
• 4.1-2 证明T (n) 2T (n / 2 n的解为O(n lg n). 证明这
c n lg( n ) c n 1 lg( n 1) (n)
22
2
2
c n lg n c n lg 2 c n 1 lg(n 1) c n 1 lg 2 (n)
2
2
2
2
c n lg n c (2n 1) c n lg(n 1) c lg(n 1) (n)
2
2
2
2
cn lg n c n lg n c n lg(n 1) c (2n 1) c lg(n 1) (n) 0
c n lg(n) c n 1lg(n 1) (n) cn lg n
22
2
2
c n lg(n) c n 1lg(n 1) (n) cn lg n 0
22
2
2
c n lg(1 1) c lg(n 1) 2n 1c (n) 0
2 n2
2
lg(1 1)是递增函数，取n 2,有lg(1 1) 1
或者修改PARTITION(A, p, r)，增加对A[i]==x时的处理。对于A[i]==x的数据， 一半放在x左边，一半放在x右边 通过设置一个flag 初始为1 当flag>0时 才进行交换 交换flag=-flag
int Partition(int A[], int p, int r)
{ int x = A[r],i=p-1; int flag = 1; for (int j = p;j< r-1;j++) { if (x >=A[i]&&flag>0)//x=A[i]时，flag大于0和小于0的数量约为一半， { swap(A[i],A[j]); } if (x ==A[i]) { flag=-flag;//这样就能让i++次数减半。 } } swap(A[i + 1],A[r]); return i + 1
取c 1/ 3，n 2时，有T (n) cn lg n,T (n) (n lg n)
所以T (n) (n lg n).
• 4.1-4证明合并排序算法的“准确”递归式(4.2)的解为
Θ(nlgn)
(1)
如果n 1
T (n) T (n / 2) T (n / 2) (n) 如果n 1
n
n
c n lg(1 1) c lg(n 1) 2n 1c (n) (n) c lg(n 1) 3n 1c
2 n2
2
2
2
c (n 1 lg(n 1)) ((1) 2c)n 2
取n 3,有n 1 lg(n 1) 0,取c 1 (1)，有((1) 2c) 0 2
c n lg(n) c n 1lg(n 1) (n) cn lg n
• [a..b]区间整数个数为C[b]-C[a-1]
• 题目已经提示运用桶排序，主要是正确设置桶
• 点均匀分布，则每个桶的尺寸应相等，即每个桶在圆中所占据的面积相等。 把圆分为n个部分，第一个部分是以原点为圆心的圆，其他部分是以原点为圆 心的圆环。
第一次作业
2.2-3 再次考虑线性查找问题 （见练习2.1-3）。在平均情况 下，需要检查输入序列中的多 少个元素？假定待查找的元素 是数组中任何一个元素的可能 性是相等的。在最坏情况下有 怎样呢？用Θ形式表示的话，线 性查找的平均情况和最坏情况 运行时间怎样？对你的答案加
以说明。
• 线性查找问题
• 输入：一列数A=<a1,a2,…,an>和一 个值v。
2
2
2
lg(n 1) lg n lg(1 1 )是递增函数，取n 1，有lg(1 1 ) 1
n
n
则有T (n) cn lg n c n c lg(n 1) 2n 1 c (n)
22
2
cn lg n c (lg(n 1) n 1) n (4(1) c)
2
2
4
取n 3，有lg(n 1) n 1 0, 取c 4(1),有4(1) c 0 2
2
n2
2
2
2
c (2 lg(n 1) n 2) n (4(1) c)
4
4
取n 3，有2 lg(n 1) n 2 0, 取c 4(1),有4(1) c 0
c n 1 lg( n 1) c n lg( n ) (n) cn lg n
2
2
22
即T (n) cn lg n
2
2
2
2
cn lg n c n(lg(n 1) lg n) c (2n 1) c lg(n 1) (n)
2
2
2
lg(n 1) lg n lg(1 1 )是递增函数，取n 2, 有 lg(1 1 ) 1
n
n
T (n) cn lg n c (3n 1) c lg(n 1) (n)
}
• 7.2-3 证明：当数组A包含不同的元素、且按降序排序时， QUICKSORT的运行时间为Θ(n2)。
• 证明：数组元素各不相同，且按降序排列时，每次递归调 用都会产生一个元素数目为n-1的分块和一个1的分块。 故有T(n)=T(n-1)+Θ(n) 有T(n)=T(n-1)+cn+d =T(n-2)+cn+c(n-1)+2d =T(n-3)+cn+c(n-1)+c(n-2)+3d =... =T(1)+cn+c(n-1)+c(n-2)+...+c(1)+nd =T(1)+cn(n+1)/2+nd =Θ(n2)
2
2
cn lg n 1 (1 c)n c lg(n 1) c 0 n
lg(n 1) lg(1 1)是递增函数，取n 2,则lg(n 1) 1
n
n
n
cn lg n 1 (1 c)n c lg(n 1) c (1 2c)n c lg(n 1) c n
取c 1/ 3,则(1 2c)n c lg(n 1) c c[n lg(n 1) 1] 0
用哨兵元素，而是在一旦数组L或R 中的所有元素都被复制回数组A后，
11. 12.
while((i<=n1) and (j<=n2)) do if L[i]<=R[j]