算法设计与分析——背诵知识点合集
前言
说在前面这是一个很无聊的博客，因为他全是要背的知识点。但是要成为大佬，不修炼点基本功怎么行。
1.算法的基本概念
1.1 算法的5个重要特性
（1）输入（2）输出（3）有穷性（4）确定性（5）可行性
1.2 算法的描述方法
自然语言、伪代码、流程图、程序设计语言
1.3算法设计的一般过程
（1）理解问题（2）选择算法设计技术（3）设计并描述算法（4）手工运行算法（5）分析算法的效率（6）实现算法
1.4重要的问题类型
（1）查找问题（2）排序问题（3）图问题（5）组合问题 （6）几何问题
2.算法分析
2.1算法的时间复杂性分析
算法的时间复杂性分析是一种事前分析估算的方法，它是对算法所消耗资源的一种渐进分析方法。所谓渐进分析是忽略具体机器、编译语言和编译器的影响，只关注在输入规模增大时算法运行时间的增长趋势。
2.1.1输入规模与基本语句
影响算法时间代价的最主要因素是输入规模。输入规模是指输入量的多少。
基本语句是执行次数与整个算法的执行次数成正比的语句。
举个例子：冒泡排序
输入规模：n
基本语句：r[j]>r[j+1]
#include<iostream>
using namespace std;
int r[5]={2,8,3,4,9};
void bubblesort(int r[5],int n)
{int bound=0,exchange=n-1;//bound表示每趟排序的待排序区间，// exchange记载每趟排序最后一次交换的位置int i,j,temp;while(exchange!=0){bound=exchange;exchange=0;for(j=0;j<bound;j++){if(r[j]>r[j+1]){temp=r[j];r[j]=r[j+1];r[j+1]=temp;exchange=j;}}}for(int i=0;i<n;i++){cout<<r[i]<<" ";}
}
int main()
{bubblesort(r,5);
}2.1.2 算法的渐进分析
算法的渐进分析不是从时间量上度量算法的运行效率，而是度量算法运行时间的增长趋势。若存在两个正的常数c和n0，对于任意n>=n0，都有T(n)<=c*f(n)，则称T（n）=O(f(n))(或称算法在O(f(n)中)。大O符号用来描述增长率的上限，表示T（n）的增长最多像f(n)增长的那样快
2.1.3 最好、最坏和平均情况
知道就行
2.1.4 非递归算法的时间复杂性分析
一般步骤：
建立一个代表算法运行时间的求和表达式，再用渐进符号表示这个表达式
2.1.5递归算法的时间复杂性分析
扩展递归是一种常用的求解递推关系式的基本技术，下面的公式记住就行，当然记不住也没关系，可以推出来。
2.2算法的空间复杂性分析
算法的空间复杂性是指在算法的执行过程中需要的辅助空间数量，也就是除算法本身和输入输出数据所占用的空间外，算法临时开辟的空间，这个辅助空间数量也应该是输入规模的函数，记作：
S（n）=O(f(n))
n为输入规模
2.3最优算法
2.3.1问题的计算复杂性下界
问题的计算复杂性下界是求解这个问题所需要的最少的工作量，求解该问题的任何算法的时间复杂性都不会低于这个下界，通常用大Ω符号来分析某个问题或某类算法的时间下界。
定义：若存在两个正的常数c和n0，对于任意n>=n0，都有T(n)>=c*g(n),则称T(n)=Ω（g(n)）
3.基本的算法设计技术
摘要：下面介绍几种算法设计技术的设计思想，纯理论，要记。
3.1蛮力法
蛮力法所依赖的基本技术是遍历，即采用一定的策略依次处理待求解问题的所有元素，从而找出问题的解。
3.2分治法
分治法将一个难以直接解决的大问题划分成一些规模较小的子问题，分别求解各个子问题，再合并子问题的解得到原问题的解。
3.3减治法
减治法将原问题分解为若干个子问题，并且原问题的解和子问题的解之间存在某种确定的关系。
3.4动态规划法
动态规划法将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段，将子问题的解求解一次并填入表中，当需要再次求解此子问题时，可以通过查表获得该子问题的解，避免了大量重复计算。
3.5贪心法
贪心法把一个复杂问题分解为一系列较为简单的局部最优选择，每一步选择都是对当前解的一个扩展，直到获得问题的完整解。贪心法在解决问题的策略上目光短浅，只根据当前已有的信息做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。
3.6回溯法
回溯法从解空间树的根结点出发，按照深度优先策略搜索满足约束条件的解。在搜索至树中某结点时，先判断该结点对应的部分解是否满足约束条件，不满足跳过以该结点为根的子树，即剪枝；否则进入以该结点为根的子树，继续按照深度优先策略进行搜索。
3.7分支界限法
分支界限法首先确定一个合理的界限函数，并根据界限函数确定目标函数的界[down,up]。然后，按照广度优先策略搜索问题的解空间树，在分支结点上依次扩展该结点的所有孩子结点，分别估算这些孩子结点的目标函数的可能取值，如果某孩子结点的目标函数的可能取值超出目标函数的界，则将其丢弃；否则，将其加入待处理结点表（PT表）中。依次从PT表中选取使目标函数取得极值的结点成为当前扩展结点，重复上述过程，直至找到最优解。