数据结构与算法分析 C语言描述(一)

一个程序问题的解决方法可以有很多，但是，在许多问题中，一个重要的概念是，写出一个可以工作的程序并不够。

当一个程序的运行时间，超过我们的接受时间时，那么这个程序是没有价值的；

或者，当一个程序所要求的空间超过我们的最大存储空间时，这个程序的算法也是不可接受的。

1.2 数学知识

指数

XAXB=XA+B

XA / XB = XA-B

(XA)B = XAB

XN + XN = 2XN ≠ X2N

对数

在计算机科学中，除非特别说明，所有对象都是以2为底的。

㏒AB = ㏒CB / ㏒CA; C > 0

㏒AB = ㏒A + ㏒B

级数

∑2i = 2N+1 – 1                   (1)

和

    ∑Ai = AN+1 – 1 / A – 1           (2)

在(2)中，若0 < A < 1，则

    ∑Ai ≦ 1 / 1 – A

模运算

如果N整除A-B，那么A与B模N同余，记为A≡B(mod N)。

例如：81≡61≡1(mod 10).

1.3 递归简论

1. 基准情形，总存在某种形，不用递归即可求解。

2. 不断推进，对于那些需要递归求解的情形，递归调用必须总能朝着产生基准情形的方向推进。