做游戏本测评的网站,济南网站设计公司富,wordpress绝对域名更改,瀑布式网站1.排序算法分类 **比较类算法排序#xff1a;**通过比较来决定元素的时间复杂度的相对次序#xff0c;由于其时间复杂度不能突破 O ( n l o g n ) O(nlogn) O(nlogn)#xff0c;因此也称为非线性时间比较类算法 **非比较类算法排序#xff1a;**不通过比较来决定元素间的…1.排序算法分类 **比较类算法排序**通过比较来决定元素的时间复杂度的相对次序由于其时间复杂度不能突破 O ( n l o g n ) O(nlogn) O(nlogn)因此也称为非线性时间比较类算法 **非比较类算法排序**不通过比较来决定元素间的相对次序它可以突破基于比较排序的时间下界以线性时间运行。
排序算法
2.排序算法性能指标
排序方法时间复杂度平均时间复杂度最坏时间复杂度最好空间复杂度稳定性插入排序 O ( n 2 ) O({n^2}) O(n2) O ( n 2 ) O({n^2}) O(n2) O ( n ) O(n) O(n) O ( 1 ) O(1) O(1)稳定希尔排序 O ( n 2 / 3 ) O(n^{2/3}) O(n2/3) O ( n 2 ) O({n^2}) O(n2) O ( n ) O(n) O(n) O ( 1 ) O(1) O(1)不稳定选择排序 O ( n 2 ) O({n^2}) O(n2) O ( n 2 ) O({n^2}) O(n2) O ( n 2 ) O({n^2}) O(n2) O ( 1 ) O(1) O(1)不稳定堆排序 O ( n l o g 2 n ) O(n{log_2}n) O(nlog2n) O ( n l o g 2 n ) O(n{log_2}n) O(nlog2n) O ( n l o g 2 n ) O(n{log_2}n) O(nlog2n) O ( 1 ) O(1) O(1)不稳定冒泡排序 O ( n 2 ) O({n^2}) O(n2) O ( n 2 ) O({n^2}) O(n2) O ( n ) O({n}) O(n) O ( 1 ) O(1) O(1)稳定快速排序 O ( n l o g 2 n ) O(n{log_2}n) O(nlog2n) O ( n 2 ) O({n^2}) O(n2) O ( n l o g 2 n ) O(n{log_2}n) O(nlog2n) O ( n l o g 2 n ) O(n{log_2}n) O(nlog2n)不稳定归并排序 O ( n l o g 2 n ) O(n{log_2}n) O(nlog2n) O ( n l o g 2 n ) O(n{log_2}n) O(nlog2n) O ( n l o g 2 n ) O(n{log_2}n) O(nlog2n) O ( n ) O(n) O(n)稳定
2.分治算法
二分: binarySearch 又叫 折半查找 是对有单调性质的数列进行查找 二分的复杂度很低达到了 O ( l o g n ) O({log_n}) O(logn) 的复杂度
模板1
int lbMIN,rbMAX;
int ans-1;
while(lbrb)
{int mid(lbrb)/2;if(check(mid)){ansmid;lbmid1;}else{rbmid-1;}printf(%d\n,ans);
}模板2
int lbMIN,rbMAX;
int mid;
while(lr)
{mid(lbrb)/2;if(check(mid)){lbmid;}else{rbmid-1;}
}
return lb;满足最小值的模板
模板一
int lbMIN,rbMAX;
int ans-1;
while(lbrb)
{int mid(lbrb)/2;if(check(mid)){ansmid;rbmid-1;}else{lbmid1;}printf(%d\n,ans);
}模板二
int lbMIN,rbMAX;
int mid;
while(lr)
{mid(lbrb)/2;if(check(mid)){rbmid;}else{lbmid1;}
}
return rb;3.倍增算法
(1)快速幂
最常见的 x y m o d m {x^y}\bmod m xymodm
typedef long long ll;
ll mypow(ll x,ll y,ll m)
{ll ans1%m;for(;y;y1){if(y1) ansans%x*m;xx*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 i1;i/*搜索分枝*/;i){/*标记该顶点已访问*/;dfs(/*下一个顶点*/);/*还原该顶点的状态*/;}
}(2)广度优先遍历
广度优先搜索算法Breadth-First Search,BFS是一种通过逐层遍历所有访问对象从而通过最短节点数到大目标的算法。
代码框架
void bfs()
{/*初始节点入队*/;while(/*队列非空*/){/*队头元素出队*/,/*赋给 current*/;while(/*current 还可以扩展*/){/*由节点 current 扩展出新节点 new*/;if(/*new 重复于已有的节点状态*/) continue;/*new 节点入队*/if(/*new 节点是目标状态*/){/*置 flagtrue*/;break;}}}
}6.动态规划DP
(1)线性动态规划
最大子段和
给出一段序列选出其中连续且非空的一段使得这一段和最大。
输入格式
第一行是一个整数 n n n 表示了序列的长度
第二行是包含 n n n 个绝对值不大于 10000 10000 10000 的整数 a i {a_i} ai 描述了这段序列。
输出格式
一个整数为最大的字段和是多少。
字段的最小长度为1.
样例输入
7
2 -4 3 -1 2 -4 3
样例输出
4
核心代码
int a[N];
int dp[N];
for(int i1;in;i)
{dpmax(dp[i-1]a[i],a[i]);ansmax(ans,dp[i]);
}最长上升子序列
一个树的序列 b i {b_i} bi 当 b 1 b 2 b 3 . . . b s {b_1}{b_2}{b_3}...{b_s} b1b2b3...bs 的时候我们称这个序列是上升的。
对于给定的一个序列 a 1 , a 2 , a 3 , . . . , a n {a_1},{a_2},{a_3},...,{a_n} a1,a2,a3,...,an我们可以得到一些上升子序列 a i 1 , a i 2 , a i 3 , . . . , a i k {a_{i1}},{a_{i2}},{a_{i3}},...,{a_{ik}} ai1,ai2,ai3,...,aik 这里 1 ≤ i 1 i 2 i 3 . . . i q ≤ N 1 \leq {i_1}{i_2}{i_3}...{i_q} \leq N 1≤i1i2i3...iq≤N
你的任务就是对于给定的序列求出最长上升序列的长度。
输入格式
输入的第一行是序列的长度 n ( 1 ≤ n ≤ 1000 ) n(1 \leq n \leq 1000) n(1≤n≤1000)。
第二行给出的序列中的 n n n 个整数这些整数的取值范围都在0到10000.
输出格式
最长上升子序列的长度。
样例输入
7
1 7 3 5 9 4 8
样例输出
4
核心代码
int a[N];
int dp[N];
for(int i1;in;i)
{dp[i]1;//附初值for(int j1;ji;j){if(a[j]a[i])//dp找最大值{dp[i]max(dp[i],dp[j]1);}}ansmax(ans,dp[i]);
}最长公共子序列
给定两个字符串 x , y x,y x,y 长度不超过5000求出两个序列的最长公共子序列。
**注意**子序列不是字串不要求连续。
输入格式
第一行一个字符串表示字符串 x x x 第二行一个字符串表示字符串 y y y。
输出格式
一个整数表示最长的公共子序列长度。
样例输入
cnblogs
belong
样例输出
4
核心代码
int c[N][N];
int len1,len2;
len1strlen(x1);
len2strlen(y1);
for(int i1;ilen1;i)
{for(int j1;jlen2;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)矩阵类动态规划
数字三角形
观察下面的数字金字塔。
写一个程序来查看从最高点到最低部任意处结束路径使路径经过数字的和最大。每一步可以走到左下方的点也可以走到右下方的点。 73 88 1 0
2 7 4 4
4 5 2 6 5
在上面的样例中从 7→3→8→7→5 的路径产生了最大和为30.
输入格式
第一行一个正整数 r r r 表示行的数目。
后面每一行为这数字金字塔特定包含的整数。
输出格式
单独一行包含那可能得到的最大的和。
样例输入
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
样例输出
30
核心代码
int dp[N][N];
for(int j1;jr;j)
{dp[r][j]a[r][j];
}
for(int ir-1;i1;i--)
{for(int j1;ji;j){dp[i][j]max(dp[i1][j],dp[i1][j1])a[i][j];}
}(3)背包问题
背包问题Knapsack problem可以描述为给定一组物品每种物品都有自己的重量和价格在限定的总重量内我们如何选择才能使得物品的总价格最高。
背包问题又分为01背包、完全背包、多重背包。此外还存在一些其他考法例如恰好装满、求方案总数、求所有的方案等。
01背包
01背包的特点就是一个物品要不就选要不就不选分别表示1和0所以叫01背包。
用 dp[i][j] 表示将前 i i i 个物品放入载重为 j j j 的背包能获得的最大价值w[i] 表示第 i i i 件物品的重量v[i] 表示第 i i i 件物品的价值则可以用一下状态转移式来表示这个过程
当 w[i]j 也即第 i i i 件物品不能放入载重为 j j j 的背包时
dp[i][j]dp[i-1][j];否则也即第 i i i 件物品能放入载重为 j j j 的背包
dp[i][j]max(dp[i-1][j],dp[i-1][j-w[i]]v[i]);注意到 dp 数组和第 i i i 行的值更新只跟 i − 1 i-1 i−1 行有关因此可以通过滚动数组结合反向更新的方式优化一下空间复杂度在动态规划解题的时候这是一种常用的空间复杂度优化方式
二维写法
for(int i1;in;i)
{for(int j0;jc;j){if(jw[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 i1;in;i)
{for(int jc;j0;j){if(jw[i]){dp[j]max(dp[j],dp[j-w[i]]v[i]);}}
}完全背包
完全背包的特点是每个东西都可以随便拿指数量 ∞ \infty ∞
用 dp[i][j] 表示将前 i i i 个物品放入载重为 j j j 的背包能获得的最大价值w[i] 表示第 i i i 件物品的重量 v[i] 表示第 i i i 个物品的价值则可以用以下的状态转移方程式来表示这个过程
当 w[i]j 也即第 i i i 件物品不能放入载重为 j j j 的背包
dp[i][j]dp[i-1][j];否则也即第 i i i 件物品能放入载重为 j j j 的背包
dp[i][j]max(dp[i-1][j],dp[i][j-w[i]]v[i]);注意如果用滚动数组的话我们需要使用正向更新方式这是唯一和上面的01背包问题的区别的地方。
二维写法
for(int i1;in;i)
{for(int j0;jc;j){if(jw[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 i1;in;i)
{for(int j0;jc;j){if(jw[i]){dp[j]max(dp[j],dp[j-w[i]]v[i]);}}
}多重背包
多重背包的特点是每种物品的数量不知一个但有限。
用 dp[i][j] 表示将前 i i i 件物品放入载重为 j j j 的背包能获得的最大价值w[i] 表示第 i i i 件物品的重量v[i] 表示第 i i i 件物品的价值s[i] 表示第 i i i 种物品的数量则可以用以下的状态转移方程式来表示这个过程
dp[i][j]max(dp[i-1][j-k*w[i]]k*v[i],0ks[i]);在多重背包的计算中可以使用二进制优化来减小时间复杂度。
for(int i1;in;i)
{for(int j0;jc;j){for(int k0;ks[i];k){if(jk*w[i]){dp[i][j]max(dp[i][j],dp[i-1][j-k*w[i]]k*v[i]);}}}
}
