上海哪家公司提供专业的网站建设,公司网站管理制定的作用,wordpress 信息字段,广州企业如何建网站排序
最好情况下#xff1a;
冒泡排序
最坏时间复杂度 O ( n 2 ) O(n^2) O(n2)。 插入排序
最坏时间复杂度为 O ( n 2 ) O(n^2) O(n2)#xff0c;最优时间复杂度为 O ( n ) O(n) O(n)。 平均情况下#xff1a;
快速排序
最坏时间复杂度为 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 ( n ) O(n) O(n)。 平均情况下
快速排序
最坏时间复杂度为 O ( n 2 ) O(n^2) O(n2)最好时间复杂度为 O ( n log n ) O(n\log n) O(nlogn)。 最坏情况下
归并排序
时间复杂度稳定为 O ( n log n ) O(n\log n) O(nlogn)。 upd on 2023/2/19
基数排序
基数排序是桶排序的扩展。它的基本思想是把整数按位切割从低位到高位排序。
具体实现就是将所有待比较数值统一为同样的数位长度数位较短的数前面补零。然后从最低位开始依次进行一次排序。从最低位排序到最高位排序完成以后数列就变成一个有序序列。 贪心
简介
贪心算法是从问题的初始状态出发通过若干次的贪心选择而得到的最优值或较优值。
贪心策略必须具备无后效性即某个状态以后的过程不会影响以前的状态至于当前状态有关。
适用前提是局部最优策略能导致全局最优策略。
基本思路
描述问题分解问题求解子问题得到局部最优解合并子问题最优解
简单贪心问题
最优装载问题 n n n 个物体第 i i i 个物体重量为 w i w_i wi选择尽量多的物体使得总重量不超过 S S S。
贪心策略先装最轻的。
部分背包问题 n n n 个物体第 i i i 个物体重量为 w i w_i wi价值为 v i v_i vi选择物体每一个物体可以只取走一部分使得总重量不超过 S S S 且总价值尽量高。
贪心策略先选出性价比高的。
乘船问题 n n n 个人第 i i i 个人重量为 w i w_i wi每艘船载重量为 C C C最多可乘两人。用最少的船装载所有人。
贪心策略最轻的人和最重的人配对。
常见应用
选择不相交区间问题
练手板子题
区间选点问题
练手板子题
将区间按照右端点的先后顺序排序依次取每个区间的右端点因为右端点可以覆盖尽量多的线段递归操作即可。
区间覆盖问题
给 n n n 个闭区间 [ a i , b i ] [a_i,b_i] [ai,bi]选择尽量少的区间覆盖一条指定的线段区间 [ s , t ] [s,t] [s,t]。
练手板子题
将所有区间的左端点从大到小排序每次选择覆盖点 s s s 的区间中右端点坐标最大的一个并将 s s s 更新为该区间的右端点坐标直到选择的区间包含 t t t 为止。
流水作业调度问题
练手板子题1
#includebits/stdc.h
using namespace std;
#define int long longstruct node
{int x,y,id;
}a[1005];int n,m,k,ans,sum; bool cmp(node xx,node yy)
{return xx.xmax(xx.y,yy.x)yy.yyy.xmax(yy.y,xx.x)xx.y;
}signed main()
{cinn; for(int i1;in;i) cina[i].x; for(int i1;in;i) cina[i].y; for(int i1;in;i) a[i].idi; sort(a1,an1,cmp); for(int i1;in;i) suma[i].x,ansmax(sum,ans)a[i].y; coutansendl;for(int i1;in;i) couta[i].idendl; return 0;
}练手板子题2
和乘船问题类似大配小即可。
#include bits/stdc.h
using namespace std;const int maxn1005;
int N,M1,M2,ans[maxn];struct node
{int id,t;friend bool operator (node a,node b){return a.tb.t;}
}mach[maxn];priority_queuenode q1;
priority_queuenode q2;int main()
{cinNM1M2;int tmp;for(int i1;iM1;i) cintmp,q1.push({tmp,tmp});for(int i1;iM2;i) cintmp,q2.push({tmp,tmp});for(int i1;iN;i){node nowq1.top();q1.pop();ans[i]now.t;q1.push({now.id,now.idnow.t});//把更新之后的时间压入}coutans[N] ;for(int iN;i;i--)//注意因为建立的是小根堆所以要倒着枚举{node nowq2.top();q2.pop();ans[i]now.t;q2.push({now.id,now.idnow.t});}sort(ans1,ansN1);coutans[N];return 0;
}带限期和罚款的单位时间任务调度问题
练手板子题
前缀和、差分
前缀和
一维前缀和 预处理 O ( n ) O(n) O(n)s[i] 统计 a 1 ∼ a i a_1\sim a_i a1∼ai 的值 for(int i1;in;i)s[i]s[i-1]a[i]查询 时间复杂度 O ( 1 ) O(1) O(1) 对于区间 [ l , r ] [l,r] [l,r] 的和用前缀和数组表示为 s r − s l − 1 s_r-s_{l-1} sr−sl−1。
二维前缀和 预处理 O ( m n ) O(mn) O(mn) for(int i1;im;i)
{for(int j1;jn;j){scanf(%d,a[i][j]);sum[i][j]sum[i-1][j]sum[i][j-1]-sum[i-1][j-1]a[i][j];}
}查询 O ( 1 ) O(1) O(1) s[i][j]第 i i i 行 j j j 列格左上部分所有元素的和。 以 ( x 1 , y 1 ) (x_1,y_1) (x1,y1) 为左上角 ( x 2 , y 2 ) (x_2,y_2) (x2,y2) 为右下角的子矩阵的和为 s ( x 2 , y 2 ) − s ( x 1 − 1 , y 2 ) − s ( x 2 , y 1 − 1 ) s ( x 1 − 1 , y 1 − 1 ) s(x_2,y_2)-s(x_1-1,y_2)-s(x_2,y_1-1)s(x_1-1,y_1-1) s(x2,y2)−s(x1−1,y2)−s(x2,y1−1)s(x1−1,y1−1)
差分
差分数组
首先给定一个原数组 a a a a 1 , a 2 , a 3 , ⋯ , a n a_1,a_2,a_3,\cdots,a_n a1,a2,a3,⋯,an然后我们构造一个数组 b b b b 1 , b 2 , b 3 ⋯ , b i b_1,b_2,b_3\cdots,b_i b1,b2,b3⋯,bi使得 a i b 1 b 2 b 3 ⋯ b i a_ib_1b_2b_3\cdotsb_i aib1b2b3⋯bi。 也就是说 a a a 数组是 b b b 数组的前缀和数组反过来我们把 b b b 数组叫做 a a a 数组的差分数组。换句话说每一个 a i a_i ai 都是 b b b 数组中从头开始的一段区间和。
差分 一维差分、 给 a a a 数组中的 [ l , r ] [l,r] [l,r] 区间中的每一个数都加上 c c c只需对差分数组 b b b 做 b[l]c,b[r1]-c 。时间复杂度为 O ( 1 ) O(1) O(1)。 二维差分 s[x1][y1]c,
s[x21][y1]-c,
s[x1][y21]-c,
s[x21][y21]c;倍增
倍增顾名思义就是成倍增长主要是在进行递推时如果状态空间很大通常的线性做法无法满足时间与空间复杂度的要求可以通过成倍增长的方式递推状态空间中在 2 2 2的整数次幂位置上的值作为代表。当需要其他位置上的值时通过“任意整数可以表示成若干个 2 2 2 的次幂项的和”这一性质使用之前求出的代表值拼成所需的值。
“倍增”与“二进制划分”思想结合降低了很多问题的时间与空间复杂度。
应用
快速幂RMQLCA
递归
卡特兰数
卡特兰数又称卡塔兰数Catalan Number是组合数学中一个常用的数列。其前几项为 1 , 2 , 5 , 14 , 42 , 132 , 429 , 1430 , 4862 , ⋯ \boxed{1,2,5,14,42,132,429,1430,4862,\cdots} 1,2,5,14,42,132,429,1430,4862,⋯
关于这个数列显然我们是找不出什么规律的所以直接把公式送给大家QwQ 递归公式 1 1 1 f ( n ) ∑ i 0 n − 1 f ( i ) × f ( n − i − 1 ) f(n)\sum_{i0}^{n-1}f(i)\times f(n-i-1) f(n)i0∑n−1f(i)×f(n−i−1) 递归公式 2 2 2 f ( n ) f ( n − 1 ) × ( 4 × n − 2 ) n 1 f(n)\dfrac{f(n-1)\times(4\times n-2)}{n1} f(n)n1f(n−1)×(4×n−2)
卡特兰数的组合数学公式详见组合数学全家桶。
汉诺塔问题
汉诺塔问题标准递归问题。
#include bits/stdc.h
using namespace std;int k0,n;void mov(int n,char a,char b,char c)
{if(n0)return;mov(n-1,a,b,c);k;coutk:from a--cendl;mov(n-1,a,c,b);
}int main()
{coutn;cinn;mov(n,a,b,c);return 0;
}函数把 n n n 片从 a a a 柱移到 c c c 柱的函数 mov(n,a,c,b)。 先调用函数 mov(n-1,a,b,c)把 n − 1 n-1 n−1 片从 a a a 柱移到 b b b 柱 c c c 柱作为过渡柱。 直接执行 把 a a a 柱上剩下的一片直接移到 c c c 上。 coutk:from a--cendl;调用 mov(n-1,b,c,a)把 b b b 柱上的 n − 1 n-1 n−1 片从 b b b 移到 c c c 柱上 a a a 柱是过渡柱。 直到减少到 n 0 n0 n0 就退出。
