《数据结构和算法分析---C语言描述》读书笔记

一、绪论

1、导致递归的四个基本法则：

（1）基准情形：必须总有某些基准情形，它无须递归就能解出，这就好比数学归纳法中的第一步，证明基本情况

（2）不断推进：每一次递归调用都必须要使求解状况朝接近基准情形的方向推进

（3）设计法则：所有的递归调用都能运行

（4）合成效益法则：在求解一个问题时，切勿在不同的递归调用中做重复的工作，

例如斐波那契序列不符合这一条，

f（n）= f（n-1）+f（n-2）

而f（n-1） = f（n-2）+f（n-3），这当中就和f（n）重复了，所以效率很低。

2、只使用处理I/O的printDigit函数编写一个过程以输出任意整数（可以是负数）

转：http://blog.****.net/fuzhengchao/article/details/7634589

1. /*打印出一个整数*/
2. voidprintOut(intn)
3. {
4. /*该整数的中间数都以正数打出*/
5. if(abs(n)>=10)
6. {
7. printOut(n/10);
8. printf("%d",abs(n%10));
9. }else//第一个数字按原样打出
10. printf("%d",n%10);
12. }
14. /*打印一个实数n，pointNum小数点位数*/
15. voidprintReal(doublen,intpointNum)
16. {
17. /*整数部分*/
18. intintPart,i,dicInt=0;
19. /*小数部分*/
20. doubledicPart;
22. intPart=n;
23. dicPart=n-intPart;
25. /*打印整数部分*/
26. printOut(intPart);
28. if(pointNum>0)
29. {
30. /*打印小数点*/
31. printf(".");
33. /*将小数部分转换为整数*/
34. for(i=0;i<pointNum;i++)
35. {
36. dicPart*=10;
37. }
39. /*小数部分符号都弄为正数*/
40. dicInt=abs(dicPart);
42. /*打印出小数部分*/
43. printOut(dicInt);
44. }
45. }

3、

1.5证明：
（1）logX<X对所有的X>0成立

令f（x） = logX/X，只需证明f(X)在X>0时小于1即可然后求导，知道当X=2时取的最大值f（x）=f（2）=1/2<1

（2）log(A的B次方)=log（A*A*......A） [共有B个A相乘]

= logA+logA+logA+.......+logA 【共有B个logA相加】

= BlogA

1.6求下列各和：

a.采用等比数列的求和公式求得Sa

b.令和=Sb，则4*Sb -Sb=3*S=1+1/4+1/(4*4)+......=Sa

c.4*Sc-Sc = ......+(i*i-(i-1)*(i-1))/(4*4...共i-1个4相乘)+....=.....+(2*i-1)/(4*4...共i-1个4相乘)......=2*Sb-Sa

d.

1.7

(1+1/2+....1/N)-(1+1/2+.....1/(N/2))=logN-log(N/2)=log2.

1.8

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
1	2	4	8	6	2	4	8	6	2	4	8	6	2	4

2(100)=2(4)(25)

2(4)的尾数为6，则mod5为1,2（100）mod5也是1

1.9
a.数学归纳法

b.数学归纳法

1.10

a.S=2*(1+2+3+......+N)-N=2*（1+N）*N/2-N = N+N*N-N=N*N

b.数学归纳法

二、算法分析

1、

2、

法则一：如果T1(N)=O(f（N）)且T2(N) = O(g（N）)，那么：

T1+T2 = max（O(f（N）) ，O（g（N）））；

T1*T2 = O（f（N）*g（N））

法则二：

如果T(N)是一个k次多项式，则T（N） =Θ（N的k次方）

法则三：

对任意常数k，（logN）的k次方 = O（N）

3、当递归正常使用时，将其转换成为一个简单的循环结构是相当困难的。

4、求序列中最大子序列和的算法：

5、对数最常出现的规律概括为：

如果一个算法用常数时间（O(1)）将问题的大小削减为其一部分，通常是1/2，那么算法就是O(logN)，另一方面，如果使用常数时间只是把问题减少为一个常数（如将问题减少1），那么这种算法就是O(N)

对分查找的时间复杂度为：O（logN）

时间复杂度为：O(logN)

6、定理：

如果M>N,则M mod N < M/2

第七行还可以写成：

return Pow（X,N-1）* X;

但是不能写成：

return Pow（Pow（X,2）,N/2）；

return Pow(Pow(X,2),N/2);

因为在N=2时，会产生无限循环，因为当N=2时，递归调用Pow中有一个是以2作为第二个参数。

同时，return Pow(X,N/2)*Pow(X,N/2);这种方式影响效率，因为产生两个递归调用。

2.1、按增长率排列 下列函数：

2/N,37，N的开方，N,NloglogN,NlogN,Nlog（N*N），NlogN*logN，N（1.5），N*N,N*N*logN，N*N*N，2（N/2），2（N）

其中NlogN,Nlog（N*N）以相同的增长率增长

2.2、

a.成立

b.不

c.不成立

d.不成立

2.3对两个数同时求对数，然后洛必达法则

2.4

罗比达法则，应用k次，最后还是为0

2.5

Let PfOO (NO) = 1 whenNO is even, and NO whenNO is odd. Likewise, let gO(NO) = 1 whenNO isodd, and NO whenNO is even. Then the ratio PfOO (NO) / g O(NO) oscillates between 0 and ∞.

2.6

（1）O(N)

(2)O(N*N)

(3)O(N*N*N)

(4)O(N*N)

(5)O(N*N*N*N*N)

(6)O(N*N*N*N)

*****************************************************************************************************************************************************************************************

2013年5月16日更新

*****************************************************************************************************************************************************************************************

三、表、栈、队列

1、

*****************************************************************************************************************************************************************************************

2013年5月16日更新

*****************************************************************************************************************************************************************************************