1.算法>排序算法分类

**比较类算法排序：**通过比较来决定元素的时间复杂度的相对次序，由于其时间复杂度不能突破 $O (n l o g n)$ ，因此也称为非线性时间比较类算法
**非比较类算法排序：**不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行。

算法>排序算法

2.算法>排序算法性能指标

排序方法	时间复杂度（平均）	时间复杂度（最坏）	时间复杂度（最好）	空间复杂度	稳定性
插入排序	$O({n^2})$	$O({n^2})$	$O (n)$	$O (1)$	稳定
希尔排序	$O(n^{2/3})$	$O({n^2})$	$O (n)$	$O (1)$	不稳定
选择排序	$O({n^2})$	$O({n^2})$	$O({n^2})$	$O (1)$	不稳定
堆排序	$O(n{log_2}n)$	$O(n{log_2}n)$	$O(n{log_2}n)$	$O (1)$	不稳定
冒泡排序	$O({n^2})$	$O({n^2})$	$O({n})$	$O (1)$	稳定
快速排序	$O(n{log_2}n)$	$O({n^2})$	$O(n{log_2}n)$	$O(n{log_2}n)$	不稳定
归并排序	$O(n{log_2}n)$	$O(n{log_2}n)$	$O(n{log_2}n)$	$O (n)$	稳定

2.分治算法

二分: binarySearch 又叫 折半查找 是对有单调性质的数列进行查找
二分的复杂度很低，达到了 $O({log_n})$ 的复杂度

模板1：

int lb=MIN,rb=MAX;
int ans=-1;
while(lb<=rb)
{
    int mid=(lb+rb)/2;
    if(check(mid))
    {
        ans=mid;
        lb=mid+1;
    }
    else
    {
        rb=mid-1;
    }
    printf("%d\n",ans);
}

模板2：

int lb=MIN,rb=MAX;
int mid;
while(l<r)
{
    mid=(lb+rb)/2;
    if(check(mid))
    {
        lb=mid;
    }
    else
    {
        rb=mid-1;
    }
}
return lb;

满足最小值的模板：

模板一：

int lb=MIN,rb=MAX;
int ans=-1;
while(lb<=rb)
{
    int mid=(lb+rb)/2;
    if(check(mid))
    {
        ans=mid;
        rb=mid-1;
    }
    else
    {
        lb=mid+1;
    }
    printf("%d\n",ans);
}

模板二：

int lb=MIN,rb=MAX;
int mid;
while(l<r)
{
    mid=(lb+rb)/2;
    if(check(mid))
    {
        rb=mid;
    }
    else
    {
        lb=mid+1;
    }
}
return rb;

3.倍增算法

(1)快速幂

最常见的 ${x^y}\bmod m$

typedef long long ll;
ll mypow(ll x,ll y,ll m)
{
    ll ans=1%m;
    for(;y;y>>1)
    {
        if(y&1) ans=ans%x*m;
        x=x*x%m;
    }
    return ans;
}

5.搜索

(1)深度优先搜索

深度优先搜索算法（英语：Depth-First Search，简称DFS）是一种用于遍历或搜索树或搜索图的算法。

深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) 。在一个HTML文件中，当一个超链被选择后，被链接的HTML文件将执行深度优先搜索，即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着HTML文件上的超链走到不能再深入为止，然后返回到某一个HTML文件，再继续选择该HTML文件中的其他超链。当不再有其他超链可选择时，说明搜索已经结束。

代码框架：

void dfs(int k)//k:当前顶点
{
    if(/*找到解 或者 没有可访问的顶点*/)
    {
        printf("%d",/*输出解*/);
        return ;
    }
    for(int i=1;i<=/*搜索分枝*/;i++)
    {
        /*标记该顶点已访问*/;
        dfs(/*下一个顶点*/);
        /*还原该顶点的状态*/;
    }
}

(2)广度优先遍历

广度优先搜索算法（Breadth-First Search,BFS）是一种通过逐层遍历所有访问对象，从而通过最短节点数到大目标的算法。

代码框架：

void bfs()
{
    /*初始节点入队*/;
    while(/*队列非空*/)
    {
        /*队头元素出队*/,/*赋给 current*/;
        while(/*current 还可以扩展*/)
        {
            /*由节点 current 扩展出新节点 new*/;
            if(/*new 重复于已有的节点状态*/) continue;
            /*new 节点入队*/
            if(/*new 节点是目标状态*/)
            {
                /*置 flag=true*/;
                break;
            }
        }
    }
}

6.动态规划（DP）

(1)线性动态规划

最大子段和

给出一段序列，选出其中连续且非空的一段使得这一段和最大。

输入格式

第一行是一个整数 $n$ ，表示了序列的长度

第二行是包含 $n$ 个绝对值不大于 $10000$ 的整数 ${a_i}$ ，描述了这段序列。

输出格式

一个整数，为最大的字段和是多少。

字段的最小长度为1.

样例输入

7

2 -4 3 -1 2 -4 3

样例输出

4

核心代码：

int a[N];
int dp[N];
for(int i=1;i<=n;i++)
{
    dp=max(dp[i-1]+a[i],a[i]);
    ans=max(ans,dp[i]);
}

最长上升子序列

一个树的序列 ${b_i}$ ，当 ${b_1}<{b_2}<{b_3}<...<{b_s}$ 的时候，我们称这个序列是上升的。

对于给定的一个序列（ ${a_1},{a_2},{a_3},...,{a_n}$ ）我们可以得到一些上升子序列 ${a_{i1}},{a_{i2}},{a_{i3}},...,{a_{ik}}$ ，这里 $\leq {i_1}<{i_2}<{i_3}<...<{i_q} \leq N$

你的任务，就是对于给定的序列，求出最长上升序列的长度。

输入格式

输入的第一行是序列的长度 $\leq n \leq 1000)$ 。

第二行给出的序列中的 $n$ 个整数，这些整数的取值范围都在0到10000.

输出格式

最长上升子序列的长度。

样例输入

7

1 7 3 5 9 4 8

样例输出

4

核心代码：

int a[N];
int dp[N];
for(int i=1;i<=n;i++)
{
    dp[i]=1;//附初值
    for(int j=1;j<i;j++)
    {
        if(a[j]<a[i])//dp找最大值
        {
            dp[i]=max(dp[i],dp[j]+1);
        }
    }
    ans=max(ans,dp[i]);
}

最长公共子序列

给定两个字符串 $x, y$ ，长度不超过5000，求出两个序列的最长公共子序列。

**注意：**子序列不是字串，不要求连续。

输入格式

第一行一个字符串，表示字符串 $x$ ，第二行一个字符串，表示字符串 $y$ 。

输出格式

一个整数，表示最长的公共子序列长度。

样例输入

cnblogs

belong

样例输出

4

核心代码：

int c[N][N];
int len1,len2;
len1=strlen(x+1);
len2=strlen(y+1);
for(int i=1;i<=len1;i++)
{
    for(int j=1;j<len2;j++)
    {
        if(x[i]==y[i])
        {
            c[i][j]=a[i-1][j]+1;
        }
        else
        {
            c[i][j]=max(c[i-1][j],c[i][j-1]);
        }
    }
}

(2)矩阵类动态规划

数字三角形

观察下面的数字金字塔。

写一个程序来查看从最高点到最低部任意处结束路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以走到右下方的点。

 7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

在上面的样例中，从 7→3→8→7→5 的路径产生了最大和，为30.

输入格式

第一行一个正整数 $r$ ，表示行的数目。

后面每一行为这数字金字塔特定包含的整数。

输出格式

单独一行，包含那可能得到的最大的和。

样例输入：

5

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

样例输出：

30

核心代码：

int dp[N][N];
for(int j=1;j<=r;j++)
{
    dp[r][j]=a[r][j];
}
for(int i=r-1;i>=1;i--)
{
    for(int j=1;j<=i;j++)
    {
        dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+a[i][j];
    }
}

(3)背包问题

背包问题（Knapsack problem）可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。

背包问题又分为：01背包、完全背包、多重背包。此外，还存在一些其他考法，例如恰好装满、求方案总数、求所有的方案等。

01背包

01背包的特点就是一个物品要不就选，要不就不选，分别表示1和0，所以叫01背包。

用 dp[i][j] 表示将前 $i$ 个物品放入载重为 $j$ 的背包能获得的最大价值，w[i] 表示第 $i$ 件物品的重量，v[i] 表示第 $i$ 件物品的价值，则可以用一下状态转移式来表示这个过程：

当 w[i]>j （也即第 $i$ 件物品不能放入载重为 $j$ 的背包）时：

dp[i][j]=dp[i-1][j];

否则（也即第 $i$ 件物品能放入载重为 $j$ 的背包）

dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);

注意到 dp 数组和第 $i$ 行的值更新只跟 $i - 1$ 行有关，因此可以通过滚动数组结合反向更新的方式优化一下空间复杂度，在动态规划解题的时候这是一种常用的空间复杂度优化方式

二维写法

for(int i=1;i<=n;i++)
{
    for(int j=0;j<=c;j++)
    {
        if(j<w[i])
        {
            dp[i][j]=dp[i-1][j];
        }
        else
        {
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
        }
    }
}

滚动数组优化

for(int i=1;i<=n;i++)
{
    for(int j=c;j>=0;j++)
    {
        if(j>=w[i])
        {
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        }
    }
}

完全背包

完全背包的特点是每个东西都可以随便拿（指数量： $\infty$ ）

用 dp[i][j] 表示将前 $i$ 个物品放入载重为 $j$ 的背包能获得的最大价值，w[i] 表示第 $i$ 件物品的重量， v[i] 表示第 $i$ 个物品的价值，则可以用以下的状态转移方程式来表示这个过程：

当 w[i]>j （也即第 $i$ 件物品不能放入载重为 $j$ 的背包）

dp[i][j]=dp[i-1][j];

否则（也即第 $i$ 件物品能放入载重为 $j$ 的背包）

dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i]);

注意如果用滚动数组的话，我们需要使用正向更新方式，这是唯一和上面的01背包问题的区别的地方。

二维写法

for(int i=1;i<=n;i++)
{
    for(int j=0;j<=c;j++)
    {
        if(j>=w[i])
        {
            dp[i][j]=max(dp[i-1][j],d[i][j-w[i]]+v[i]);
        }
        else
        {
            dp[i][j]=dp[i-1][j];
        }
    }
}

滚动数组优化

for(int i=1;i<=n;i++)
{
    for(int j=0;j<=c;j++)
    {
        if(j>=w[i])
        {
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        }
    }
}

多重背包

多重背包的特点是每种物品的数量不知一个，但有限。

用 dp[i][j] 表示将前 $i$ 件物品放入载重为 $j$ 的背包能获得的最大价值，w[i] 表示第 $i$ 件物品的重量，v[i] 表示第 $i$ 件物品的价值，s[i] 表示第 $i$ 种物品的数量，则可以用以下的状态转移方程式来表示这个过程：

dp[i][j]=max(dp[i-1][j-k*w[i]]+k*v[i],0<=k<=s[i]);

在多重背包的计算中，可以使用二进制优化来减小时间复杂度。

for(int i=1;i<=n;i++)
{
    for(int j=0;j<=c;j++)
    {
        for(int k=0;k<=s[i];k++)
        {
            if(j>=k*w[i])
            {
                dp[i][j]=max(dp[i][j],dp[i-1][j-k*w[i]]+k*v[i]);
            }
        }
    }
}

排序算法概述

1.算法>排序算法分类

算法>排序算法

2.算法>排序算法性能指标

2.分治算法

模板1：

模板2：

满足最小值的模板：

3.倍增算法

(1)快速幂

5.搜索

(1)深度优先搜索

(2)广度优先遍历

6.动态规划（DP）

(1)线性动态规划

输入格式

输出格式

样例输入

样例输出

输入格式

输出格式

样例输入

样例输出

输入格式

输出格式

样例输入

样例输出

(2)矩阵类动态规划

输入格式

输出格式

样例输入：

样例输出：

(3)背包问题

相关文章