算法概述
从应用范围来看,算法可以分为数值算法和非数值算法.从工作方式来看,算法可以分为串行算法和并行算法.
概念
算法就是对特定问题求解过程的描述.
算法有一下几种性质:
- 通用性:
对符合输入要求的任意数据能够进行问题求解并能得到正确答案. - 有效性
每条指令都能够正确有效的执行,执行结果类型可以预期. - 确定性
每一步之后都有关于下一步动作的确切指令 - 有穷性
算法的执行必须在有限步数内执行完毕. - 输入输出性
算法必须要有输入输出,没有输入输出的算法是无意义的.
算法设计
1 . 穷举法
将问题空间中所有的求解对象一一列举出来,然后逐一分析求解.
2.回溯法
将问题的候选解按某一顺序逐一枚举,检验来寻找满足条件的解,当候选解不可能是问题解时,返回上一步重新选择下一个解.放弃当前候选解选择下一个候选解的过程叫做回溯,扩大当前候选解的规模,以继续向前试探的过程叫做向前试探.
3.分治法和递归法
遇到一个难以解决的大问题就把它分成规模小的问题并逐个击破.再把子问题的解合并得出整个问题的解.分治会导致多个相同类型的子问题这会导致递归过程的发生.
4.贪心法和动态规划
贪心法就是从问题的初始状态出发,依靠某种贪心策略进行若干次贪心选择得到最优解(较优解).通过局部最优得到全局最优.
动态规划分出的子问题大多不是相互独立的.若用分治法则得到的子问题太多,且相同的子问题被多次计算.如果可以保存子问题的答案就可以避免大量重复的计算.一般用一个表记录所有子问题的答案,不管该子问题之后是否会用到都会记录在该表上.
5.迭代法
迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程，跟迭代法相对应的是直接法（或者称为一次解法），即一次性解决问题。迭代法又分为精确迭代和近似迭代。“二分法”和“牛顿迭代法”属于近似迭代法。迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。
6.分支定界法
分支定界法的基本思想是对有约束条件的最优化问题的所有可行解（数目有限）空间进行搜索。该算法在具体执行时，把全部可行的解空间不断分割为越来越小的子集（称为分支），并为每个子集内的解的值计算一个下界或上界（称为定界）。在每次分支后，对凡是界限超出已知可行解值那些子集不再做进一步分支，这样，解的许多子集（即搜索树上的许多结点）就可以不予考虑了，从而缩小了搜索范围。这一过程一直进行到找出可行解为止，该可行解的值不大于任何子集的界限。因此这种算法一般可以求得最优解。
算法设计的一般步骤
问题描述
问题分析和抽象
数据结构与算法设计
算法分析
