算法分析-C语言描述

这个系列争取在12天以内完结

本教程默认您熟悉递归的运用，以及高中基本数学知识（数论，离散数学）。

递归四条基本法则：

1，基准情形。必须有某些基准情形，他们不需要递归就能求解。

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

3，设计法则。假设所有递归调用都能运行。

4，合成效益法则。在求解一个问题的同意实例时，切勿再不同的递归调用中做重复性工作。

递归不仅简化了算法设计，也有助于写出更简洁的代码。但递归的效率并不是很理想，不合理的递归程序在内存开销方面也是很占空间的（虽然现在计算机的内存比较大，但数据量变的特别庞大以后就也难说了）。

 递归函数再结束之前会一直在栈区开辟空间，一直到基准条件（如果没有基准条件会一直执行）

斐波那契数的计算：

//递归方式
int func(int n)
{
	if (n == 1 || n == 2)
	{
		return 1;
	}
	else
	{
		return func(n - 1) + func(n - 2);
	}
}
//循环方式
for (int i = 0; i < n; ++i)
	{
		f1 = f1 +f2;
		f2 = f1+ f2;
	}

递归调用是恐怖的指数级增长O（2的n次方），而for循环仅仅是常数级O（N）；大可输入48试一试。

3，一般法则

1，for/while循环：一层便是循环次数，二层便是M*N，即O（M*N),M = N时，耗时O（N²），除非特殊情况否则我们绝对不可以写出超过O（N²）的算法，O（N²）也要尽量写成O（logN）（默认以2为底）

        

        O(M)

        for（int i = 0;i

       

        O(M*N)

        for(int i = 0;i

                for(int j = 0;j

2，顺序语句：仅算最长时间。

        如下顺序执行为O(N²)

        

        for（int i = 0;i

        ...

        for(int i = 0;i

                for(int j = 0;j

                ...

        if/else只看语句内运行的最长时间

附上一般教科书都会有的几个数据结构题：

由于作者Ubuntu系统镜像损坏导致代码丢失，只剩下AVL树的源码，其他的我会后续发布。。。大家一定要做好有用的代码备份。