以下为《算法复习提纲(1)(1)》的无排版文字预览，完整格式请下载

下载前请仔细阅读文字预览以及下方图片预览。图片预览是什么样的，下载的文档就是什么样的。

什么是算法？

算法就是做事的方法或者叫计算机程序中表达的方法。也是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。算法应该具有以下五个重要的特征：有穷性、确切性、输入、输出、可行性

算法的复杂性，时间复杂度的计算方法？

算法的复杂性有时间复杂性和空间复杂性两种。其作用： 时间复杂度是指执行算法所需要的计算工作量；而空间复杂度是指执行这个算法所需要的内存空间。

时间复杂度用来表示算法的快慢。时间复杂度的计算方法:先找出算法的基本操作，然后根据相应的各语句确定它的执行次数，再找出T（n）的同数量级（它的同数量级有以下：1，Log2n ，n ，nLog2n ，n的平方，n的三次方，2的n次方，n！），找出后，f（n）=该数量级，若T(n)/f(n)求极限可得到一常数c，则时间复杂度T（n）=O（f（n））。

递归算法的优缺点

递归就是让程序调用自身的一种编程技巧。

优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。

缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。

分治法（二分法）:基本思想:指的是每次的查找范围折半。与枚举算法相比，二分查找比较次数少，查找速度快，平均性能好的优点。其缺点是要求待查的数据已被整理为有序列表。

方程求解:P84

在线翻译:P85

动态规划

将一个问题分解为子问题递归求解，并且将中间结果保存以避免重复计算的办法，可以称为‘动态规划’。动态规划通常用来求最优解。能用动态规划解决的求最优解问题，必须满足最优解的每个局部解也都是最优的。P137

解题思路:用动态规划解题，首先要把原问题分解为若干个子问题。

往往将和子问题相关的各个变量的一组取值称为一个”状态”。一个“状态”对应一个或多个子问题。

满足以下两个条件的问题才可以用动态规划的办法求解:问题具有最优子结构性质。无后效性。

贪心算法:贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择。也就是说，不从整体最优上加以考虑，做出的只是在某种意义上的局部最优解 。

斐波那契数列:斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=1，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）

深度优先搜索:深度优先搜索属于图算法的一种，是一个针对图和树的遍历算法。深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。一般用堆数据结构来辅助实现DFS算法。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。

完美立方:一个3 = B 3 + C 3 + d 3为完美立方等式。例如12 3 = 6 3 + 8 3 + 10 3 。编写一个程序，对任给的正整数N（N ≤ 100） ，寻找所有的四元组（A，b，C，d） ，使得 内容过长，仅展示头部和尾部部分文字预览，全文请查看图片预览。 盘从 a 移到 b。

当 n>1 时，需要利用 b，将 n-1 个圆盘移到 c 上，然后将剩下的最大圆盘移到 b

最后利用 a，将 n-1 个较小的圆盘从 c 移到 b 上（递归子问题 n-1）。

我们将n个圆盘的移动问题就分解成了两次 n-1 个圆盘的移动问题。

递归算法：

public static void hanoi(int n,int a,int b,int c){

if(n==1){

move(a,b);

}else{

hanoi(n-1,a,c,b);

move(a,b);

hanoi(n-1,c,b,a);

}

}

[文章尾部最后300字内容到此结束,中间部分内容请查看底下的图片预览]

以上为《算法复习提纲(1)(1)》的无排版文字预览，完整格式请下载

下载前请仔细阅读上面文字预览以及下方图片预览。图片预览是什么样的，下载的文档就是什么样的。