算法设计与分析——背诵知识点合集_算法设计与分析知识点

前言

说在前面这是一个很无聊的博客，因为他全是要背的知识点。但是要成为大佬，不修炼点基本功怎么行。

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表中选取使目标函数取得极值的结点成为当前扩展结点，重复上述过程，直至找到最优解。