算法复杂性
算法是指对特定问题求解步骤的一种描述。
算法具有以下特性：
- 有穷性：算法是由若干条指令组成的有穷序列，总是在执行若干次后结束，不可能永不停止。
- 确定性：每条语句有确定的含义，无歧义。
- 可行性：算法在当前环境条件下可以通过有限次运算实现。
- 输入输出：有零个或多个输入，一个或多个输出。
时间复杂度：
算法运行需要的时间，一般将算法的执行次数作为时间复杂度的度量标准。
//算法 1-3
sum=0; //运行1次
total=0;//运行1次
for(i=1;i<=n;i++)//运行n次
{
sum=sum+i;//运行n次
for(j=1;j<=n;j++)//运行n*(n+1)次
total=total+i;//运行n*n次
}把算法的所有语句的运行次数加起来：1+1+n+1+n+n×(n+1)+n×n，可以用一个函数T(n)表达：
$$
T(n)=2n^2+3n+3
$$
当n足够大时,我们可以看到算法运行时间主要取决于第一项，后面的甚至可以忽略不计。
用极限表示为：
$$
\lim_{n\rightarrow\infty}\frac{T(n)}{f(n)}=C≠0，C为不等于0的常数
$$
如果用时间复杂度的渐近上界表示，如图1-1所示。
从图1-1中可以看出，当n≥n0时，T(m)≤Cf(n)，当n足够大时，T(n)和f(n)近似相等。因此，我们用O(f(n))来表示时间复杂度渐近上界，通常用这种表示法衡量算法时间复杂度。算法1-3的时间复杂度渐近上界为O(f(n))=O(n^2)，用极限表示为：
$$
\lim_{n\rightarrow\infty}\frac{T(n)}{f(n)}=\frac{2n^2+3n+3}{n^2}=2≠0
$$
还有渐近下界符号Ω(T(n)≥Cf(n))，如图1-2所示。
从图1-2可以看出，当n≥n0时，T(n)≥Cf(n)，当n足够大时，T(n)和f(n)近似相等，因此，我们用Ω(f(n))来表示时间复杂度渐近下界。
渐近精确界符号Θ(C1f(n)≤T(n)≤C2f(n))，如图1-3所示。
从图1-3中可以看出，当n≥n0时，C1f(n)≤T(n)≤C2f(n)，当n足够大时，T(n)和f(n)近似相等。这种两边逼近的方式，更加精确近似，因此，用
Θ(f(n))来表示时间复杂度渐近精确界。
我们通常使用时间复杂度渐近上界O(f(n))来表示时间复杂度。
//算法1-4
i=1;//运行1次
while(i<=n)//可假设运行x次
{
i=i*2;//可假设运行x次
}观察算法1-4，无法立即确定while及i=i*2运行了多少次。这时可假设运行了x次，每次运算后i值为2，2^2，2^3，…，2^x，当i=n时结束，即2^x=n时结束，则x=log2(n)，那么算法1-4的运算次数为1+2log2(n)，时间复杂度渐近上界为O(f(n))=O(log2(n))。
注意：不是每个算法都能直接计算运行次数
有些算法，如排序、查找、插入等算法，可以分为最好、最坏和平均情况分别求算法渐近复杂度，但我们考查一个算法通常考查最坏的情况，而不是考查最好的情况，最坏情况对衡量算法的好坏具有实际的意义。
空间复杂度：
算法占用的空间大小。一般将算法的辅助空间作为衡量空间复杂度的标准。
空间复杂度的本意是指算法在运行过程中占用了多少存储空间。算法占用的存储空间包括：
- 输入/输出数据
- 算法本身
- 额外需要的辅助空间
输入输出数据占用的空间是必需的，算法本身占用的空间可以通过精简算法来缩减，但这个压缩的量是很小的，可以忽略不计。而在运行时使用的辅助变量所占用的空间，即辅助空间是衡量空间复杂度的关键因素。
//算法1-6
swap(int x,int y)//x与y交换
{
int temp;
temp=x;//temp为辅助空间
x=y;
y=temp;
}该算法使用了一个辅助空间temp，空间复杂度为O(1)。
注意：递归算法中，每一次递推需要一个栈空间来保存调用记录，因此，空间复杂度需要计算递归栈的辅助空间。
//算法1-7
fac(int n)
{
if(n<0)
{
printf("n<0 data error!");
return -1;
}
else if(n == 0 || n == 1)
return 1;
else
return n*fac(n-1);
}斐波那契数列：
根据斐波那契数列的定义，直接设计一个递归算法：
Fib1(int n)
{
if(n<1)
return -1;
if(n == 1 || n ==2)
return 1;
return Fib1(n-1)+Fib1(n-2);
}因此，n>2时要分别调用Fib1(n-1)、Fib1(n-2)和执行一次加法运算，即：
n>2时，T(n) = T(n-1) + T(n-2) + 1;
递归表达式和时间复杂度T(n)之间的关系如下：
由此可得：T(n)≥F(n)。
由于T(n)≥F(n)，这是一个指数阶的算法！复杂度属于爆炸增量函数，这在算法设计时应当避开的，那么我们可以改进它呢？
既然斐波那契数列中的每一项是前两项之和，如果记录前两项的值，只需要一次加法运算就可以得到当前项，时间复杂度会不会更低一些？我们用数组试试看：
Fib2(int n)
{
if(n < 1)
return -1;
int *a = new int[n];
a[1] = 1;
a[2] = 1;
for(int i=3;i<=n;i++)
a[i] = a[i-1]+a[i-2];
return a[n];
}很明显，算法的时间复杂度为O(n)。时间复杂度却从指数阶降到了多项式阶，这是算法效率的一个巨大突破！
其实我们只需要得到第n个斐波那契数，中间结果只是为了下一次使用，根本不需要记录。因此我们采用迭代法进行算法设计：
Fib3(int n)
{
int i,s1,s2;
if(n<1)
return -1;
if(n == 1 || n ==2)
return 1;
s1=1;
s2=1;
for(i=3; i<=n; i++)
{
s2=s1+s2;//辗转相加法
s1=s2-s1;//记录前一项
}
return s2;
}进一步讨论：我们能不能继续降阶，使算法时间复杂度更低呢？
本文摘录于《趣学算法》一书，欲学习其他算法请购买正版书籍！