算法概述1.1算法和程序算法是由几个指令组成的穷举序列，满足以下四个性质：
(1)输入)作为算法的输入，外部给定的量有零个以上。
(2)输出)算法生成至少一个量作为输出。
(3)确定性：构成算法的各命令清晰，无歧义。
(4)有限性：算法中每条指令的执行次数有限，每条指令的执行时间也有限。
问题：由输入和输出的关系定义
算法：将问题输入转换为输出的计算过程
程序：用编程语言实现算法
程序时算法的计算机高级描述，是算法的具体实现；算法更可看成是程序的灵魂。程序可以不满足算法性质的第四条有限性。
*
有几种方法可以描述算法。
自然语言方式、表方式、图形形式等
C和自然语言相结合的方式
数据结构是算法的基础
算法确定如何构建数据
算法和数据结构等于程序
*算法设计的一般步骤：
1 .分析问题，建立数学模型
2 .梳理相关已知知识，分解问题
3 .设计算法，建立初步解
4 .对设计的算法进行正确性证明
5 .有效分析正确的算法
6 .用程序实现分析后的算法
7 .相关文档的完善。
空间复杂性：
考虑空间复杂性的理由：
在多用户系统上运行时，必须指定分配给程序的内存大小。
我想事先知道计算机系统是否有足够的内存运行程序
一个问题可能有几种不同的内存要求解决方案。 从其中选择。
用空间复杂度估计一个程序可以解决的问题的最大规模。
程序与算法不同，是用某种编程语言具体实现算法的，程序可以不满足算法的性质(4)。
描述算法有自然语言方式、表示方式等各种方式。
算法复杂性的高低体现在运行该算法所需的计算机资源的多寡上，所需资源越多，该算法的复杂性就越高；相反，所需资源越少，算法的复杂性就越低。 对于计算机资源来说，最重要的是时间和空间，即存储资源。 因此，算法的复杂度既有时间复杂度，也有空间复杂度。
算法的复杂性是指执行算法所需的计算机资源的量，需要时间资源的量称为时间复杂性，需要空间资源的量称为空间复杂性。 这个量应该集中反映算法的效率，并从运行该算法的实际计算机中抽象出来。 换句话说，这个量应该是依赖于要解决的问题的规模、算法的输入和算法本身的函数。
算法求解问题的规模、算法的输入、算法本身分别用n、I、a表示，且复杂度用c表示，则有c=f(n，I，a )。 这里，f ) n，I，a )是由n，I，a确定的三元函数。 时间复杂性t=t(n，I，a )和s=s (n，I，a )。 通常，a隐藏在复杂性函数名中，所以将t和s分别简称为t=t(n，I )和s=s ) n，I )。
累进符号
以下讨论用f(n )表示一个程序的时间或空间复杂度。 这是实例特征n (一般为输入范围)的函数。
由于程序的时间或空间要求为非负实数，因此也可以假设函数f(n )对于n的所有值为非负实数，并假设n=0
渐进码o的定义：存在正数常数c和自然数N0，使得当n大于等于N0时f(n )小于等于CG ) n，g ) n为函数f ) n的一个上界，f(n )=o ) g(n )，即f(n )的阶数为g )。
用于比较的函数g(n )应该尽可能接近所考虑的函数f ) n )
递归和分治策略直接或间接调用自身的算法称为递归算法。 由函数本身给出定义的函数称为递归函数。 分治法产生的子问题往往是原问题的小模式，便于使用递归技术。 在这种情况下，通过反复应用分治的方法，可以使原问题和子问题的类型一致，但其规模继续缩小，最终可以缩小到容易直接求出其解的程度。 这自然会导致递归过程的发生。
分治和递归像孪生兄弟，往往同时应用于算法设计，从而产生许多高效算法。
阶乘函数阶乘函数可以递归定义
边界条件和递归方程是递归函数的两个要素，递归函数只有具备这两个要求，才能在有限次计算后得出结果。
Fibonacci数列
intFibonacci(intn ) if (n=1) return 1； returnFibonacci(n-1 ) Fibonacci (n-2 )； } Ackerman函数
如果函数及其变量是由函数本身定义的，则该函数称为双重递归函数。
Ackerman函数a(n，m )是a (1，0 )=2，a ) 0，m )=1，a ) n，0 )=(N2 ) n=2，a ) n，m ) ) n-1，m
罗列问题
设计递归算法生成n个要素{r1，r2，rn}的全排列。
# includeiostreamusingnamespacestd； void P
erm(int list[],int k,int m){if(k == m){for(int i=0;i<=m;i++) cout<<list[i];cout<<endl;}else{for(int i=k;i<=m;i++){swap(list[k],list[i]);Perm(list,k+1,m);swap(list[k],list[i]);}}}void swap(int &a,int &b){int temp = a;a = b;b = temp;} int main(){int a[3] = {1,2,3};Perm(a,0,2);return 0; }整数划分问题
将正整数n表示成一系列之和，n=n1+n2+n3…+nn
可建立q(n,m)的如下递归关系。
代码实现
Hanoi塔问题
void hanio(int n ,int a,int b,int c ){if(n>0){hanio(n-1,a,c,b);move(a,b);hanio(n-1.c,b,a);}}递归小结
优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大的方便。
缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。
在具体处理过程中存在明显的不同:递归方法是采用自顶向下的方式产生计算序列，这个过程可能导致许多重复的调用，这也是递归算法效率较低的主要原因之一；而递推采用自底向上的方式产生计算序列，使每一步新产生的计算结果总是建立子啊已有结果的基础上，避免了许多重复的计算。利用子问题已有的解构造规模较大子问题的解，进而构造原问题的解，因而比递归算法具有更高的效率。
分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题相会独立且与原问题相同。递归地解这些子问题，然后将各子问题的解合并得到原来的解。
分治法的基本步骤：(1)分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
（2）解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题。
（3）合并：将各个子问题的解合并为原问题的解。
分治法所能解决的问题一般具有以下几个特征：
该问题的规模缩小到一定的程度就可以容易地解决；
该问题可以分解为若干个规模较小的相同问题；
利用该问题分解出的子问题的解可以合并为该问题的解；
该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。
二分搜索技术
大整数的乘法
设计一个有效的算法，求两个n位二进制大整数的乘积