龙岗公司做网站,深圳app网站,上海东方网首页,梧州单身相亲网站目录
2.2 栈底#xff08;bottom#xff09;
}
大数乘大数
节点#xff1a;包含一个数据元素及若干指向子树分支的信息 。
节点的度#xff1a;一个节点拥有子树的数目称为节点的度 。
叶子节点#xff1a;也称为终端节点#xff0c;没有子树的节点或者度为零的节点…目录
2.2 栈底bottom
}
大数乘大数
节点包含一个数据元素及若干指向子树分支的信息 。
节点的度一个节点拥有子树的数目称为节点的度 。
叶子节点也称为终端节点没有子树的节点或者度为零的节点。
分支节点也称为非终端节点度不为零的节点称为非终端节点 。
树的度树中所有节点的度的最大值。
节点的层次从根节点开始假设根节点为第1层根节点的子节点为第2层依此类推如果某一个节点位于第L层则其子节点位于第L1层 。
树的深度也称为树的高度树中所有节点的层次最大值称为树的深度 。
有序树如果树中各棵子树的次序是有先后次序则称该树为有序树。
无序树如果树中各棵子树的次序没有先后次序则称该树为无序树。
森林由mm≥0棵互不相交的树构成一片森林。如果把一棵非空的树的根节点删除则该树就变成了一片森林森林中的树由原来根节点的各棵子树构成。
二叉树的节点数量
二叉树的遍历
先序遍历
中序遍历
二叉树遍历的总结
特殊的二叉树
二叉搜索树
平衡二叉树
二分查找
二分查找也称折半查找 Binary Search它是一种效率较高的查找方法。但是折半查找要求线性表必须采用顺序存储结构而且表中元素按关键字有序排列。
二分查找的基本思想
STL与二分查找
upper_bound
lower_bound
二分查找的适用条件
二分答案的思想
二分答案的技巧
二分答案适用的条件
链表的分类
单向链表
链表的常用操作
查找操作
插入操作 链表与数组
数组的插入
数组的删除
链表的应用
Vector
遍历vector
队列
map的功能
使用map
定义
set的定义
添加元素
正序遍历
set s;
set::iterator it;
for (it s.begin(); it ! s.end(); it)
cout *it endl;
反序遍历 容器与迭代器
vectorstack,queuemapset都是stl提供的标准数据结构他们共同的特点是都是容器用来存储元素集合。为了统一他们的使用方法stl提供了迭代器。
康托展开
康托展开运算
康托展开逆运算
康托展开是一个全排列到一个自然数的双射因此是可逆的。即对于上述例子在给出61可以算出起排列组合为34152。由上述的计算过程逆推回来具体过程如下
位运算
“按位与”运算符
左移运算符
右移运算符
顾名思义枚举便是依次列举出所有可能产生的结果根据题中的条件对所得的结果进行逐一的判断过滤掉那些不符合要求的保留那些符合要求的也可以称之为暴力算法。
枚举法的优缺点
时间复杂度
空间复杂度
常见算法复杂度
复杂度分析基础
复杂度分析进阶
空间换时间
常用的空间换时间方法
前缀和优化
ST表
XOR的特性
尺取法
概念 尺取法也常被称为双指针是很常用的一种优化算法。通常是对数组保存一对下标即所选取的区间的左右端点然后根据实际情况不断地推进区间左右端点以得出答案。尺取法比直接暴力枚举区间效率高很多。
适用条件
贪心算法
贪心算法进阶
贪心的适用条件 栈
stack的基本操作
在C的标准库中 有封装好的栈 stack stack 是一个模板类定义stack的示例代码如下
stack类型 对象
stackint s;
一种常见的数据结构遵循后进先出先进后出的原则。有一个连续的内存区域组成栈顶top
线性表允许插入和删除的那一段。值得注意的是栈顶指针top的指向是有些两种方式的一种是指向栈顶当前元素一种是指向栈顶的下一位置。两种指向方式对栈的操作影响不大只是在判断栈顶位置的时候略有差异本文以指向当前栈顶元素为例。另一种指向方式读者可以自行实践。
2.2 栈底bottom
固定的不允许进行插入和删除的另一端。 进栈 push topn Top 退栈pop
Topn; Top--
#define n 100
int top0,x;
void push(int 2[],x){
if(topn)
else top;
s[top]x;
}
void pop(int s[]){
if(top0) {
coutunderflow;
}
Else{top--;
} } int stackArray[1000], index -1;
void push(int x) { index; stackArray[index] x;
}
int pop() { int value stackArray[index]; index--; return value;
}
int top( ) { return stackArray[index];
}
int size( ) { return index 1;
}
int main( ) { push(1); push(2); push(3); cout 顶: top() endl; cout 大小: size() endl; pop(); cout 顶: top() endl; cout 大小: size() endl; pop(); cout 顶: top() endl; cout 大小: size() endl; pop(); return 0;
} 操作 代码 解释 入栈 s.push(x) 将x元素入栈 出栈 s.pop() 弹出栈的第一个元素并不会返回元素的值 栈顶元素 s.top() 获取栈的第一个元素 元素个数 s.size() 获取栈中的元素个数返回int 判空 s.empty() 栈是否为空返回bool相当于s.size() 0
汉诺塔
void hanoi(int n,char a,char b,char c){
if(n1){
couta--cendl;
}else{
hanoi(n-1,a,c,b);
couta--cendl;
hanoi(n-1,b,a,c); }}
int main(){
int n; cinn;
hanoi(n,A,B,C);
return 0} 高精度数大数 分类 整形数组 字符数组 储存方式 按字符串输入通过循环语句将字符转换位数字 直接输入以字符方式存储 获取位数 计算每个数组的元素位数再相加 strlen( )函数 输出 采用循环语句打印数组元素 字符串输出方便 运算 直接计算 转化为数字后计算
Strlen Strrev
高精度加法
#include bits/stdc.h
using namespace std;
int main() {
char a1[5005], b1[5005];
int a[5005], b[5005], c[5005];
int lena, lenb, lenc 1, x, i;
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
memset(c, 0, sizeof(c));
cina1b1;
lena strlen(a1);
lenb strlen(b1);
for(i0; ilena; i) a[lena - i] a1[i] - 0;
for(i0; ilenb; i) b[lenb - i] b1[i] - 0;
x 0;
while(lenc lena || lenc lenb) {
c[lenc] a[lenc] b[lenc] x;
x c[lenc] / 10;
c[lenc] % 10;
lenc;
}
c[lenc] x;
if(c[lenc] 0) {
lenc--;
}
for(int ilenc; i1; i--) {
cout c[i];
}
return 0;
}高精度减法
strcmp 比较compare
Strcpy 复制copy
char a1[1001]{},b1[1001]{},c1[1001]{};
int a[1001]{},b[1001]{},c[1001]{};
int lena,lenb,lenc0,i;
cina1b1;
lenastrlen(a1);
lenbstrlen(b1);
if(strlen(a1)strlen(b1)||(strlen(a1)strlen(b1)strcmp(a1,b1)0)){
strcpy(c1,a1);
strcpy(a1,b1);
strcpy(b1,c1);
cout-;
}
lenastrlen(a1);
lenbstrlen(b1);
for(i0;ilena;i){
a[lena-i-1]a1[i]-48;
}
for(i0;ilenb;i){
b[lenb-i-1]b1[i]-48;
}
i0;
while(ilena||ilenb){
if(a[i]b[i]){
a[i]10;
a[i1]--;
}
c[i]a[i]-b[i];
i;
}
lenci;
while((c[lenc]0)(lenc1)){
lenc--;
}
for(ilenc;i0;i--){
coutc[i];
}
coutendl;
高精度乘法
输入被乘数和乘数。将char类型的被乘数转化为int 类型。将乘数与被乘数各个位相乘计算并处理进位。输出乘积。
(多位乘一位
char a[201]{};
int a1[201],b1[202],b,x0,s;
cinab;
if(b0){
cout0;
return 0;
}
int lenstrlen(a);
for(int i0;ilen;i){
a1[i1]a[i]-48;
}
for(int ilen;i0;i--){
sa1[i]*bx;
b1[i]s%10;
xs/10;
}
int i0;
while(b1[i]0 ilen){
i;
}
for(i;ilen;i){
coutb1[i];
}
大数乘大数
当乘数和被乘数都是大数时套用上面大数乘 intint 的方法逐个计算并进位最终合并相加。
例如 6789854321238763×77198343712321636789854321238763×7719834371232163 转换后 6789854321238763 6789|8543|2123|8763 7719834371232163 7719|8343|7123|2163 8763 67641597|73109709|62418849|18954369 进位 6764|8908|5951|0744|4369 2123 16387437|17712189|15122129|4592049 进位 1638|9208|3701|2588|2049 8543 65943417|71274249|60851789|18478509 进位 6595|0545|0334|3636|8509 6789 52404291|56640627|48358047|14684607 进位 5240|9955|5462|9515|4607
最后进行位移相加 6764 8908 5951 0744 4369 1638 9208 3701 2588 2049 6595 0545 0334 3636 8509 5240 9955 5462 9515 4607 5241 6550 7647 5823 0853 7048 2793 4369
多位乘多位
int main(){
char a1[1001]{},b1[1001]{};
int a[1001]{},b[1001]{},c[2002]{};
cina1b1;
int lenastrlen(a1);
int lenbstrlen(b1);
for(int i0;ilena;i){
a[lena-i]a1[i]-48;
}
for(int i0;ilenb;i){
b[lenb-i]b1[i]-48;
}
for(int i1;ilenb;i){
int x0;
for(int j1;jlena;j){
c[ji-1]a[j]*b[i]xc[ij-1];
xc[ij-1]/10;
c[ij-1]%10;
}
c[ilena]x;
}
int lenclenalenb;
while(c[lenc]0lenc1){
lenc--;
}
for(int ilenc;i0;i--){
coutc[i];
}
return 0;
}
两个数相乘积不可能超过两数位数之和。 a1[1001]{ },b1[1001]{ },c[2002]{}
高精度除法
高精除高精
#includebits/stdc.h
using namespace std;
int a[101],b[101],c[101],d,i;
void init(int a[]){
string s;
cins;
a[0]s.length();
for(i1;ia[0];i)
a[i]s[a[0]-i]-0;
}
void print(int a[]){
if(a[0]0) {
cout0endl;
return ;
}
for(int ia[0];i0;i--) couta[i];
coutendl;
return ;
}
int compare(int a[],int b[]){
if(a[0]b[0]) return 1;
if(a[0]b[0]) return -1;
for(int ia[0];i0;i--){
if(a[i]b[i]) return 1;
if(a[i]b[i]) return -1;
}
return 0;
}
void jian(int a[],int b[]){
int flag,i;
flagcompare(a,b);
if(flag0) {a[0]0;return;}
if(flag1){
for(i1;ia[0];i){
if(a[i]b[i]){
a[i1]--;
a[i]10;
}
a[i]-b[i];
}
while(a[0]0a[a[0]]0) a[0]--;
return;
}
}
void numcpy(int p[],int q[],int det){
for(int i1;ip[0];i)q[idet-1]p[i];
q[0]p[0]det-1;
}
void chu(int a[],int b[],int c[]){
int i,tmp[101];
c[0]a[0]-b[0]1;
for(ic[0];i0;i--){
memset(tmp,0,sizeof(tmp));
numcpy(b,tmp,i);
while(compare(a,tmp)0){
c[i];
jian(a,tmp);
}
}
while(c[0]0c[c[0]]0) c[0]--;
return ;
}
int main(){
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
init(a);
init(b);
chu(a,b,c);
print(c);
print(a);
return 0;
}排序
冒泡排序 快速排序 选择排序 二叉树排序
插入排序 堆排排序 选择排序
每一趟从待排序的数据元素中选出最大或最小的一个元素顺序放在待排序的数列的最前面直到全部待排序的数据元素排完。
读入数据存放在a数组中。在a[1]~a[n]中选择值最小的元素与第1位置元素进行交换则把最小值元素放入a[1]中。在a[2]~a[n]中选择值最小的元素与第2位置元素进行交换则把最小元素放入a[2]中。知道第n-1个元素与第n 个元素比较排序为止。
int n,k,i,j;
int a[1001];
cinn;
for(i0;in;i){
cina[i];
}
for(i0;in;i){
ki;
for(ji1;jn;j){
if(a[j]a[k]){
kj;
}
}
if(k!i){
swap(a[i],a[k]);
}
}
for(i0;in;i){
couta[i] ;
}
冒泡排序
读入数据存放在a数组中。比较相邻的前后两个数据如果前面数据大于后面的数据就将两个数据交换。对数组的第0个数据到n-1个数据进行一次遍历后最大的一个数据就“冒”到数组第n-1个位置。重复前面第二步至道排序完成。
int n,k,i,j;
int a[1001];
cinn;
for(i0;in;i){
cina[i];
}
for(in-1;i1;i--){
for(j0;ji;j){
if(a[j]a[j1]){
swap(a[j],a[j1]);
}}}
for(i0;in;i){
couta[i] ;
} 6 5 3 4 1 2 5 6 3 4 1 2 5 3 6 4 1 2 5 3 4 6 1 2 5 3 4 1 6 2 5 3 4 1 2 6 图
邻接数组表示法
图是一种非线性的数据结构有多点连接在一起。图是由有限个数的顶点和顶点之间边的组成通常表示为:G(V,E),其中G表示一个图V是图G中顶点的集合E是图G中边的集合。
无向图在途中任一顶点上的边都是没有方向性的。
无向边的表示用圆括号将两端的顶点括起来ViVj).
有向图在图中任意顶点上的边都是有方向的。
有向边的表示用尖括号将边两边的顶点括起来Vi,Vj
有向完全图有向图中如果任意两个顶点之间都存在方向互为相反的两条弧。含有n个顶点的有向完全图有n*n-1条边。
无向完全图无向图中任意两个顶点之间都存在边。含有n个顶点的无向完全图有n*(n-1)/2条边。
子图图形中取出的部分集合。
度顶点V的度是和V相关联的边的数目。
入度有向图中以顶点V为终点的有向图边的数目。
出度有向图中以顶点V为起点的有向边的数目。
权值边的“费用”可以形象的理解为边的长度。
回路起点和终点相同的路径称为回路。或“环”
连通图形在无向图中任意两个顶点皆连通则称为连通图形。即任意两个顶点皆存在一条路径可到达。
强连通图形在有向图中任意两个顶点间皆存在一条路径可到对方则称为强连通图形。
强连通分量有向图中任意两点都连通的最大子图包括单个顶点。 邻接数组
邻接数组表示法是以一个n*n的数组来表示一个具有n个顶点的图形我们以数组的索引值来表示顶点以数组的内容值来表示顶点间的边是否存在。如图所示 0 1 2 3 4 0 0 1 1 0 0 1 1 0 1 1 1 2 1 1 0 1 0 3 0 1 1 0 0 4 0 1 0 0 0
遍历从图中某一顶点出发系统的访问图中的所有顶点是每个顶点恰好被访问一边。
树
由n(0)个元素组成的有限集合每个元素称为结点有一个特定的结点称为根结点。
除了根节点外其余节点称为子树。一个结点的子树个数称为这个结点的度。度为0的结点称为叶节点.
二叉树度为二。二叉树的每个结点最多有两个结点。
在二叉树的第i层上最多有2i-1个结点。i1)
深度为k的二叉数至多有2k-1个结点。(k1)
满二叉树除最后一层无结点外每一层上的所有结点都有两个子结点。在满二叉树中每一层上的结点数都达到最大值。
完全二叉树除最后一层外每一层上的结点数均达最大值在最后一层上只缺少右边的若干结点。 二叉树
在计算机科学中二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”。 节点 左子树 右子树 0 子树 1 子树 7 1 子树 2 子树 6 2 无 无
链表也可以看作是一棵特殊的二叉树因为链表每个结点只有一个子节点满足二叉树的定义。二叉树与普通树的差别在于普通树可以有 22 个以上的子节点而二叉树的子节点不能超过 22 个。 链表 二叉树 树 后继节点 1个 不超过 2个 任意个 定义关系 链表属于二叉树 二叉树属于树
节点包含一个数据元素及若干指向子树分支的信息 。
节点的度一个节点拥有子树的数目称为节点的度 。
叶子节点也称为终端节点没有子树的节点或者度为零的节点。
分支节点也称为非终端节点度不为零的节点称为非终端节点 。
树的度树中所有节点的度的最大值。
节点的层次从根节点开始假设根节点为第1层根节点的子节点为第2层依此类推如果某一个节点位于第L层则其子节点位于第L1层 。
树的深度也称为树的高度树中所有节点的层次最大值称为树的深度 。
有序树如果树中各棵子树的次序是有先后次序则称该树为有序树。
无序树如果树中各棵子树的次序没有先后次序则称该树为无序树。
森林由mm≥0棵互不相交的树构成一片森林。如果把一棵非空的树的根节点删除则该树就变成了一片森林森林中的树由原来根节点的各棵子树构成。
二叉树的节点数量
一棵高度为n的二叉树最多包括2n−1个节点。树高为n共有n 层第一层有1 个根节点根据二叉树的定义后面每层节点的数量最多为上一层的2 倍因此最多有124....2n−12n−1个节点。 上图为一棵高度为3的二叉树共有7个节点。
那么一棵高度为n的二叉树最少包括多少个节点呢最少有n个节点是一个链表。
二叉树的存储
可以继续沿用存储树的方法来存储二叉树。
struct node{ int value; vectorint childs; //用来记录所有子节点的编号
}nodes[10000];
int root;
//root为根节点
也可以利用二叉树的特性用左右子树的方式来存储二叉树。
用结构体来表示二叉树的节点 每个节点存储了当前节点的值 以及左子树和右子树的编号。
struct node{ int value; int left; int right;
}nodes[10000];
int root; //root为根节点
二叉树的遍历
遍历二叉树的方法可以沿用遍历树的方法——递归。
DFS(当前节点u){ DFS(u.left); DFS(u.right);
}
在此基础上二叉树的遍历又分为以下三种 顺序 先序遍历 根左右 27,14,10,19,35,31,42 中序遍历 左根右 10,14,19,27,31,35,42 后序遍历 左右根 10,19,14,31,42,35,27
先序遍历
遍历顺序规则为根左右遍历方法
1访问根节点
2采用先序递归遍历左子树
3采用先序递归遍历右子树 先序遍历结果ABDFECGHI。
中序遍历 遍历顺序规则为左根右遍历方法
1采用中序遍历左子树
2访问根节点
3采用中序遍历右子树 中序遍历结果 DBEF A GHCI。
二叉树遍历的总结
三种方法遍历过程中经过节点的路线一样只是访问各个节点的顺序不同。
二叉树的先序、中序、后序遍历我们已经学会了 那么给定其中任意两种遍历 我们能否推出唯一的第三种遍历么?
答案给定先序中序可以推出后序。后序中序可以推出先序。但是先序后序是无法推出中序的。
这里我们只是以知道先序遍历和中序遍历推断后序遍历作为例子其他组合方式原理是一样的。
要完成这个任务我们首先要利用以下几个特性
特性A对于先序遍历第一个肯定是根节点
特性B对于后序遍历最后一个肯定是根节点
特性C利用先序或后序遍历确定根节点在中序遍历中根节点的两边就可以分出左子树和右子树
特性D对左子树和右子树分别做前面3点的分析和拆分相当于做递归我们就可以重建出完整的二叉树。
所以我们可以靠保存先序中序或者后序中序2个顺序来保存整个二叉树的结构。
以下为先序遍历结果为1,2,3的所有二叉树。 编号 中序 后序 1 3,2,1 3,2,1 2 1,2,3 3,2,1 3 2,3,1 3,2,1 4 2,1,3 2,3,1 5 1,3,2 3,2,1
上面的表格中所有的中序遍历结果都不相同因此给出中序就可以确定是哪棵二叉树。
但后序遍历的结果有重复的情况因此如果给出后序遍历的结果并不能确定对应的是哪一棵二叉树。
特殊的二叉树
二叉搜索树
二叉搜索树Binary Search Tree又二叉排序树它或者是一棵空树或者是具有下列性质的二叉树 若它的左子树不空则左子树上所有节点的值均小于它的根节点的值 若它的右子树不空则右子树上所有节点的值均大于它的根节点的值 它的左、右子树也分别为二叉搜索树。 上图为二叉搜索树以子树20为例左子树的节点包括3,14。均小于20右子树的节点包括35。大于20。二叉搜索树是特殊的二叉树因为除了满足二叉的条件之外还满足节点有序。二叉搜索树有许多扩展被用于各类数据结构。因为在二叉查找树中找一个符合条件的值时间复杂度同这个树的深度相关。而我们知道假如这个二叉搜索树的每一个节点都是满的其所有叶子节点的深度都是 d 那么这棵树的节点数量可以达到O(2d)。这时查找的复杂度为O(log(n))。与我们之前学习的二分查找复杂度相同。能够快速查找数据也是二叉搜索树被用于各类数据结构的原因但这种快速是有限制的即不会出现退化假如二叉搜索树退化为链表则无法做到快速查找数据的要求所以又出现了平衡二叉树。
平衡二叉树
平衡二叉树Balanced Binary Tree具有以下性质它是一棵空树或它的左右两个子树的高度差的绝对值不超过1并且左右两个子树都是一棵平衡二叉树。
平衡二叉树有效的限制了树高使得二叉树不会退化为一个链表。
平衡二叉树如果同时也是一棵二叉搜索树那么查找某个节点的效率是O(log(n))的。
很多数据结构不能完美的做到平衡但也能有效的控制树高例如红黑树。也被经常用于数据的快速查找。
根据后序找出根节点e。根据中序确定左右子树。确定左右子树根节点。
满二叉数有2k-1个结点
struct node{
char value;
int left,right;
}data[101];
int root0,cnt;
char ch;
int buildTree(int bt){
cinch;
if(ch.){
bt0;
return bt;
}else{
btcnt;
data[bt].valuech;
data[bt].leftdata[bt].right0;
data[bt].leftbuildTree(bt);
data[bt].rightbuildTree(bt);
}
return bt;
}
void postorder(int bt){
if(bt){
postorder(data[bt].left);
postorder(data[bt].right);
coutdata[bt].value;
}
}
int main(){
root0;
cnt0;
rootbuildTree(0);
postorder(root);
return 0;
} 共同特点
最优子结构
母问题的最优解包含其子问题的最优解我们就称此问题具有最优子结构。
子问题重叠
子问题本质上是和母问题一样的只是问题的输入参数不一样就可以称之为子问题重叠。 这类问题的解决途径------【动态规划】
背包问题
int w[200],c[200],f[200][200];
int m,n;
cinmn;
for(int i1;in;i){
cinw[i]c[i];
}
for(int i1;in;i){
for(int j1;jm;j){
if(jw[i]){
f[i][j]max(f[i-1][j-w[i]]c[i],f[i-1][j]);
}else{
f[i][j]f[i-1][j];
}
}
}
coutf[n][m]; 算法
算法是对特定问题求解步骤的一种描述他是指令的有限序列其中那个每一条指令表示一个或多个操作。简单来说算法就是解决问题的操作步骤。
1有穷性 2确定性 3输入 4输出 5可行性
时间复杂度 计算工作量
空间复杂度 内存空间
结构顺序结构 选择结构 循环结构 算法
划分阶段按照问题的特征把问题分为若干个阶段。确定状态和状态变量将问题发展到各个阶段所处的各种情况用不同的状态表示出来。确定决策并写出状态转移方程根据相邻状态之间的关系确定决策。寻找边界条件递推式的边界条件。 特征 具体描述 有穷性 对于任意一组合法的输入值算法的每个操做步骤都蒙在有限时间内完成 确定性 算法中的每一步都必须是有明确的定义不允许歧义性和多义性 输入 一个算法应该有0个或多个输入以刻画预算对象的初始情况。 输出 一个算法应该有一个或多个输出以反映对输入数据加工后的结果 可行性 在特定的接替规则中允许使用的可执行的并可以通过执行有限次来实现。 二分法
每次找一半 优先级括号非与或、异或。 int maxline200,kz;
int reverse(char s[]){
int i,j,t;
for(i0,jstrlen(s)-1;ij;i,j--){
ts[i];s[i]s[j];s[j]t;
}
return 0;}
int main(){
char line[100];
cinkz;
while(kz!-1){
cinline;
reverse(line);
coutlineendl;
cinkz; }
return 0;} 二分查找
二分查找也称折半查找 Binary Search它是一种效率较高的查找方法。但是折半查找要求线性表必须采用顺序存储结构而且表中元素按关键字有序排列。
给一个不重复有序的数组 要找到某一个数出现的位置 最朴素的做法就是遍历一遍数组 复杂度是O(n)但是通过二分查找 可以在O(log(n))的复杂度下完成查找。如数组123456789 查找元素6用二分查找的算法执行的话其顺序为第一步查找中间元素即5由于56则 6 必然在5之后的数组元素中那么就在6789中查找寻找6789 的中位数为 7 76 则6应该在7左边的数组元素中那么只剩下6即找到了。
二分查找的基本思想
A想好一个100以内的自然数由B来猜。每次A都会告诉B猜大了还是小了或者猜对了。B的最优策略就是先猜50如果大了再猜25如果小了则猜75。这就用到了二分查找的思想。设 R[low..high]是当前的查找区间首先确定该区间的中点位置mid⌊(lowhigh)/2⌋。然后将待查的K值与 a[mid] 比较若相等则查找成功并返回此位置否则须确定新的查找区间继续二分查找具体方法如下若a[mid]K则由表的有序性可知a[mid..n]均大于K因此若表中存在关键字等于K的结点则该结点必定是在位置 mid 左边的子表a[low..mid−1]中故新的查找区间是左子表R[low..mid−1]。若a[mid]K则要查找的K必在mid 的右子表R[mid1..high]中即新的查找区间是右子表 R[mid1..high]。下一次查找是针对新的查找区间进行的。因此从初始的查找区间R[1..n]开始每经过一次与当前查找区间的中点位置上的结点关键字的比较就可确定查找是否成功不成功则当前的查找区间就缩小一半。这一过程重复直至找到关键字为 KK 的结点或者直至当前的查找区间为空(即查找失败)时为止。 因为每次都可以将区间大小缩小一半所以最多只需log(n)log(n) 次就可完成查找所以二分查找的复杂度是O(log(n))。
int Binary_Search(int a[], int n, int key){ int low, high, mid; low 1; /*定义最底下标为记录首位*/ high n; /*定义最高下标为记录末位*/ while (low high) { mid (low high) / 2; /*折半*/ if (key a[mid]) high mid - 1; else if (key a[mid]) low mid 1; else return mid; } return -1; // 没找到
}
STL与二分查找
upper_bound
upper_bound() 是 CC 标准库提供的二分查找函数可以在一个排好序的数组中对指定数值进行查找。
upper_bound(begin,end,num)会从数组的 begin 位置到 end−1 位置二分查找第一个大于num的数字。同排序sort函数一样upper_bound()提供了一个重载函数允许我们自己定义什么是大于upper_bound(begin,end,num,cmp)。通过cmp函数定于大于或小于。需要注意:如果原数组不是通过 cmp 进行排序的则不符合二分的条件因为二分查找过程中会认为原数组是无序的。upper_bound()最终返回的是一个地址即第一个大于num 的数字的位置如果不存在则返回end 。通过返回的地址减去起始地址begin 得到找到数字在数组中的下标。
int main(){ int num[6]{1,2,4,7,15,34}; sort(num, num 6); //按从小到大排序 int pos upper_bound(num, num 6, 7) - num;//返回数组中第一个大于被查数的值 cout pos num[pos] endl; return 0;
}
输出结果如下4 15
使用自定义的比较函数 cmpcmp 。
int cmp(int a,int b){ return a b;
}
int main(){ int num[6]{34, 15, 7, 4, 2, 1}; sort(num, num 6, cmp); //按从大到小排序 int posupper_bound(num, num6, 7, cmp) - num; //返回数组中第一个小于被查数的值 cout pos num[pos] endl; return 0;
}
输出结果3 4
lower_bound
lower_bound()是C标准库提供的另一个二分查找函数与upper_bound() lower_bound(begin,end,num)会从数组的begin位置到end−1 位置二分查找第一个大于或等于num的数字。
lower_bound()也提供了一个重载函数允许我们自己定义什么是大于lower_bound(begin,end,num,cmp) 。 数组 返回 upper_bound() 必须有序 大于 numnum 的数 lower_bound() 必须有序 大于或等于 numnum 的数
int main(){ int num[6]{1,2,4,7,15,34}; sort(num,num6); //按从小到大排序 int poslower_bound(num, num6,7) - num; //返回数组中第一个大于或等于被查数的值 coutpos num[pos]endl; return 0;
}
输出结果3 7
使用自定义的比较函数 cmpcmp 。
int cmp(int a,int b){ return a b;
}
int main(){ int num[6]{34, 15, 7, 4, 2, 1}; sort(num, num 6, cmp); //按从大到小排序 int pos lower_bound(num, num 6, 7, cmp) - num; //返回数组中第一个小于或等于被查数的值 cout pos num[pos] endl; return 0;
}
输出结果2 7
二分查找的适用条件
虽然二分查找的效率高但是要将表按关键字排序。而排序本身是一种很费时的运算。如果所给的数组无序的则需要先用的复杂度将数组进行排序才能完成二分查找。
二分答案的思想
二分答案就是对最终答案的值进行二分具体做法就是每次取一个中间答案 把答案作为已知条件 判断根据当前答案是否满足题意 根据判断结果再将区间缩小。写法和二分查找基本相同 只不过要判断的东西比较复杂 一般写法是通过写一个\(check\) 函数来实现。
二分答案的技巧
二分答案通常是在寻找“合法”与“不合法”的边界进一步说是在寻找“刚好合法”的那个位置。二分离不开单调性我们做这类题目最重要的就是要找到题目中的某个与“合法性”有单调关系的量。单调关系通常可以表现为A越大越合法A越小越不合法。在题目中总结出这种单调关系十分有助于进一步思考。
二分答案适用的条件
一个问题如果可以用二分答案的方法来解决一定要满足某种单调性。这样通过二分答案我们可以将一个本来需要复杂计算的问题转为一个判定性问题即成立或不成立没有严格的单调性保障二分答案可能会给出错误的答案。 链表
链表是一种物理存储单元上非连续非顺序的储存结构数据元素的逻辑顺序是通过链表中的指针连续实现的。
单向链表数据以节点来表示只能一个方向
双向链表每个数据节点中都有两个指针可以两个方向
循环链表表中最后一个结点的指针域指向头节点整个链表形成一个环。 数组是在内存中一段连续的存储空间 可以在常数时间内访问任意位置的元素 但是数组也有缺点 无法做到快速的插入和删除 因为空间是连续且固定的 想要在 p 位置插入/删除一个元素 则 p 之后的位置的元素都需要移动。
为了能够在常数时间内实现元素的插入和删除 我们引入 链表 这种数据结构。
链表是一种物理存储单元上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点链表中每一个元素称为结点组成结点可以在运行时动态生成。
那么非连续、非线性有什么含义呢这表明链表的内存是不连续的前一个元素存储地址的下一个地址中存储的不一定是下一个元素。链表通过一个指向下一个元素地址的引用将链表中的元素串起来。
链表的分类 分类 描述 单向链表 每一个节点包含了数据块和指向下一个节点的指针 双向链表 每一个节点包含了数据块和指向下一个节点的指针以及指向前一个节点的指针
单向链表
单向链表是最简单的链表形式。我们将链表中最基本的数据称为节点(node)每一个节点包含了数据块data和指向下一个节点的指针next链表有一个头节点图中以head表示。可以看出head指向第一个元素第一个元素的next又指向第二个元素……直到最后一个元素该元素不再指向其他元素它称为表尾它的 next 为空NULL链表到此结束。 可以看到要找链表中的某一元素必须先找到上一个元素根据它提供的下一个元素的地址才能找到下一个元素。如果不提供头指针则整个链表都无法访问。链表如同一条铁链一样一环扣一环中间是不能断开的。
我们使用数组模拟的方法来学习链表。我们创建一个结构体 这个结构体有两个int型的变量分别是data和nextdata就是链表当前节点存储的数据next指向下一个节点的节点编号在数组中的编号这样可以避免使用指针。
struct node{ //next即后面节点的编号data就是需要维护的数据 int next,data;
}a[10000];
int head; //head即头指针
//head节点是头结点 不存储数据 作用只是用来找到链表的第一个节点。
链表的常用操作 操作 描述 查找 找到符合条件的节点 插入 添加一个新节点 删除 删除一个存在的节点
查找操作
如何根据给出的数据找到链表中符合条件的节点呢需要从头节点开始逐个向后遍历节点比较 p 的 data 同待查找的数据是否相同相同则返回当前节点。 struct node{ //next即后面节点的编号data就是需要维护的数据 int next,data;
}a[10000];
int head; //head即头节点的编号
node find(int value){ int p head; //从 while(a[p] ! NULL) { if(valuea[p].data) return a[p]; p a[p].next; } return NULL;
}
插入操作 链表与数组 操作 链表 数组 查找 从头节点开始查找 从下标0开始查找 插入 很快因为只需要修改pre以及新节点的next编号 所有后面的节点都要向后移1位 删除 很快因为只需要修改pre的next编号 所有后面的节点都要向前移1位
数组的插入 数组的删除 链表的应用
由于链表存储不连续一般来讲访问效率低于数组。但链表的删除插入效率高。 欧拉回路奇数点可各遍历一遍。
捆绑法插空法排除
STL 标准模板库 obj.pop_back()删除数组中的最后一个数据 typede起别名 Insert 添加函数 Vector只关心随机存取不在乎插入和删除
List 只关心插入删除不在乎随机存取。
动态规划
int main(){
int a[101][101];
for(int i0;i8;i){
for(int j1;i8;j){
if(i1j1){
a[i][j]1;
}else{
a[i][j]a[i-1][j]a[i][j-1];
}
}
}
couta[8][8]; 深搜能深则深不能深就退。 Vector
基本操作
vectorint c
c.clear() //移除容器中所有数据。
c.empty() //判断容器是否为空。
c.erase(pos) //删除pos位置的数据
c.erase(beg,end) //删除[beg,end)区间的数据
c.front() //传回第一个数据。
c.insert(pos,elem) //在pos位置插入一个elem拷贝
c.pop_back() //删除最后一个数据。
c.push_back(elem) //在尾部加入一个数据。
c.resize(num) //重新设置该容器的大小
c.size() //回容器中实际数据的个数。
c.begin() //返回指向容器第一个元素的迭代器
c.end() //返回指向容器最后一个元素的迭代器
遍历vector
访问 vector 的方法有两种
方法一直接访问
方法二迭代器访问
int main(){ //顺序访问 vectorintobj; for (int i 0; i 10; i) obj.push_back(i); cout 直接利用下标; for (int i 0; i obj.size(); i)//方法一 cout obj[i] ; cout endl; cout 利用迭代器; //声明一个迭代器来访问vector容器作用遍历或者指向vector容器的元素 vectorint::iterator it;
for(it obj.begin();it ! obj.end(); it) cout *it ; return 0;} 队列
队列是一种特殊的线性表。队列的原则是先进先出FIFO — first in first out。先进先出来后进后出。
队列在队头做删除操作在队尾做插入操作
队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队从队列中删除一个队列元素称为出队。因为队列只允许在一端插入在另一端删除所以只有最早进入队列的元素才能最先从队列中删除故队列又称为先进先出FIFO—first in first out线性表。 操作 函数 解释 入队 push(x) 将x元素入队 出队 pop() 弹出队首元素返回值为队首元素值 元素个数 size() 获取队列中的元素个数返回int 获取队首元素 front() 获取队列第一个元素 在 C的标准库中 有封装好的队列 queue,queue是一个模板类定义 queue 对象的示例代码如下 queueint q1; queuedouble q2; 操作 代码 解释 入队 q.push(x) 将x元素放到队列的末端 出队 q.pop() 弹出队列的第一个元素并不会返回元素的值 队首元素 q.front() 获取队列的第一个元素 队尾元素 q.back() 获取队列的最后一个元素 元素个数 q.size() 获取队中的元素个数返回int 判空 q.empty() 队列是否为空返回bool相当于q.size() 0
int main() { queueint q; //定义队列q q.push(1); //放入元素3 q.push(2); q.push(3); cout 头: q.front( ) endl; cout 尾: q.back( ) endl; cout 大小: q.size( ) endl; q.pop(); //弹出队列的第一个元素 cout 头: q.front( ) endl; cout 尾: q.back( ) endl; cout 大小: q.size( ) endl; q.pop( ); cout 头: q.front( ) endl; cout 尾: q.back( ) endl; cout 大小: q.size( ) endl; q.pop( ); return 0;
} MAP
map是C标准库的一个关联容器是一个模板类。
它提供一对一其中第一个可以称为关键字每个关键字只能在 map中出现一次第二个可能称为该关键字的值的数据处理能力由于这个特性,它完成有可能在我们处理一对一数据的时候在编程上提供快速通道。map就是从键 key到值value的映射。因为重载了[ ][ ]运算符map像是数组的“高级版”。
例如可以用一个 mapstring intmonth_name 来表示“月份名字到月份编号”的映射然后用 monthname[July]7 这样的方式来赋值。
这里说下map 内部数据的组织map 内部自建一颗红黑树(一 种非严格意义上的平衡二叉树)这颗树具有对数据自动排序的功能所以在map 内部所有的数据都是有序的后边我们会见识到有序的好处。map 是一类关联式容器。它的特点是增加和删除节点对迭代器的影响很小除了那个操作节点对其他的节点都没有什么影响。
如果没有map利用结构体数组查找某个键对应的值就需要遍历整个数组这样很低效。map的内部实现是一种名为红黑树的数据结构当将不同的键值放入 map这种数据结构会自动将所有键值变为有序的按照键key排序。
如放入8[A],1[F],7[Y],4[L],10[X]后中括号内为值map中保存的数据顺序为 1[F],4[L],7[Y],8[A],10[X] 。
因为有序当我们查找某个值的时候就无须遍历整个数组而是可以用二分的方法快速定位。还是以上面的数据为例我们想要查找4对应的值查找过程会先找到中间的7,发现7比4大因而只在前一半中进行查找这样每次查找的范围会缩小一半关于二分的知识我们会在后续课程中讲解这里不展开介绍。
map并不是唯一支持从 key 找 value的数据结构还有一种更快的以空间换时间的方法叫做 hash。
map的功能
自动建立Keyvalue 的对应。key和value可以是任意你需要的类型。
根据key值快速查找记录查找的复杂度基本是Log(N)Log(N)
1.快速插入Key−Value记录
2.快速删除记录。
3.根据Key修改
.value记录
4.遍历所有记录。
使用map
定义
mapstring,int my_Map; SET关联式容器
set作为一个容器也是用来存储同一数据类型的数据类型并且能从一个数据集合中取出数据在 set中每个元素的值都唯一而且系统能根据元素的值自动进行排序。应该注意的是 set 中数元素的值不能直接被改变。与 map的使用方法大致都相同。
set的定义
set类型 对象名; 如setint s;
添加元素
setint s;
s.insert(8);
s.insert(10);
s.insert(6);
s.insert(8); //重复元素不会插入
set遍历
setset 的遍历也是使用迭代器进行遍历 可以正序遍历也可以反序遍历。
正序遍历
setint s;
setint::iterator it;
for (it s.begin(); it ! s.end(); it)
cout *it endl;
反序遍历
setint::reverse_iterator it;
for (it s.rbegin(); it ! s.rend(); it) cout *it endl 容器与迭代器
vectorstack,queuemapset都是stl提供的标准数据结构他们共同的特点是都是容器用来存储元素集合。为了统一他们的使用方法stl提供了迭代器。 容器 迭代器功能 解释 vector 随机访问 deque 随机访问 双端队列可以从前后push,pop 元素 list 双向 链表 set/multiset 双向 multiset是允许有重复元素的set元素保持有序 map/multimap 双向 multimap是允许有重复元素的map元素是pair保持有序 stack 不支持迭代器 栈 queue 不支持迭代器 队列 priority_queue 不支持迭代器 优先队列每次可以从栈顶取出当前最小 容器 添加元素的效率 删除元素的效率 查找元素 访问中间的元素
递归
在函数内部可以调用其他函数。如果一个函数在内部调用自己本身这个函数就是递归函数。如果一个函数在调用自己则被调用的”自己”再调用“自己”。想象一下这将会无限循环下去所以递归函数中肯定有办法在某种情况下停止调用自己即停止递归一般来说使用if语句实现在满足特定的条件下终止递归。
函数不再递归的情况称作基本情形base case,也称基本情况。函数调用自身来执行子任务的情况就称作递归情形recursive case。
操作格式
递归函数格式如下
函数类型 函数名(形参1){ if(条件1 该条件下的函数值; else if(条件2 另一种条件下的函数值; ...... 执行操作并进行递归调用;
}
递归与辗转相除
辗转相除法又名欧几里德算法。是求最大公约数的一种方法。它的具体做法是用较大数除以较小数再用出现的余数第一余数去除除数再用出现的余数第二余数去除第一余数如此反复直到最后余数是0为止。如果是求两个数的最大公约数那么最后的除数就是这两个数的最大公约数。
int gcd(int a, int b) { if (b 0) return a; return gcd(b, a % b);
}
递归替代循环
void printHello(int n) { // 传入一个参数n if(n 0) return; cout Hello endl; printHello(n - 1);
}
int main() { // 主函数 printHello(5); // 调用函数
}
循环替代递归
斐波那契数列
int Fib(int n){ int a 1, b 1; for (int i 2; i n; i){ int t b; b a; a t; } return a;
}
int main(){ cout Fib(10);
return 0;
}
康托展开
康托展开是一个全排列到一个自然数的双射常用于构建哈希表时的空间压缩。 康托展开的实质是计算当前排列在所有由小到大全排列中的顺序因此是可逆的。
康托展开运算
Xan(n−1)!an−1(n−2)!...a10!其中ai为整数并且满足0≤aii,1≤i≤nai表示原数的第i位在当前未出现的元素中排在第几。
例在12345的排列组合中计算34152的康托展开值。 值 未出现且小于当前值的数 展开值 33 1,2a52 a5×4! 4848 44 1,2a42 a4×3! 1212 11 无 a30a30 a3×2!a3×2! 00 55 2a212a21 a2×1!a2×1! 11 22 无 a10a10 a1×0!a1×0! 00
所以比34152小的组合有61个即34152是排第62。
康托展开逆运算
康托展开是一个全排列到一个自然数的双射因此是可逆的。即对于上述例子在给出61可以算出起排列组合为34152。由上述的计算过程逆推回来具体过程如下
61/4!2余13说明,说明比首位小的数有2个所以首位为3 。
13/3!2余11说明说明在第二位之后小于第二位的数有2 个所以第二位为4。
1/2!0余1说明说明在第三位之后没有小于第三位的数所以第三位为1。
用1/1!1余0说明说明在第四位之后小于第四位的数有1个所以第四位为5。
最后一位自然就是剩下的数2。通过以上分析所求排列组合为34152 。
位运算
位运算是指按二进制进行的运算。在系统软件中常常需要处理二进制位的问题。C语言提供了6 个位操作运算符。这些运算符只能用于整型操作数即只能用于带符号或无符号的 char,short,int与longlong 类型。 运算符 按位与 如果两个相应的二进制位都为1则该位的结果值为1否则为0 | 按位或 两个相应的二进制位中只要有一个为1该位的结果值为1 ^ 按位异或 若参加运算的两个二进制位值相同则为0否则为1 ~ 取反 ~是一元运算符用来对一个二进制数按位取反将0变1将1变0 左移 用来将一个数的各二进制位全部左移N位右补0 右移 将一个数的各二进制位右移N位移到右端的低位被舍弃对于无符号数高位补0
“按位与”运算符
参加运算的两个数据按二进制位进行“与”运算。如果两个相应的二进制位都为 1 则该位的结果值为 1 。否则为 0 。 按位与and) 111 100 010 000
00101 11100
以前我们判断一个数n是奇数还是偶数通常使用n%2的结果来判断1为奇数0为偶数现在我们也可以使用 操作来判断奇偶n1的结果就是取n的二进制的最末位。二进制的最末位为0表示n为偶数最末位为1表示n为奇数。
位运算应用
左移运算符
左移运算符是用来将一个数的各二进制位左移若干位移动的位数由右操作数指定右操作数必须是非负值其右边空出的位用 00 填补高位左移溢出则舍弃该高位。
例如将a的二进制数左移2位右边空出的位补0左边溢出的位舍弃。若a15 即(00001111)2左移2位得(00111100) 。
左移1位相当于该数乘以2左移2位相当于该数乘以2×24 。
15260即乘了4。但此结论只适用于该数左移时被溢出舍弃的高位中不包含 1的情况。
右移运算符
右移一位相当于除以2右移n位相当于除以2n。
在右移时需要注意符号位问题。对无符号数右移时左边高位移入0。对于有符号的值如果原来符号位为0该数为正则左边也是移入0如果上例表示的那样如果符号位原来为1该数为负则左边移入的0 还是1要取决于所用的计算机系统。移入0称为 逻辑右移即简单右移。移入1称为算术右移。最后一位直接去掉。 简单枚举
顾名思义枚举便是依次列举出所有可能产生的结果根据题中的条件对所得的结果进行逐一的判断过滤掉那些不符合要求的保留那些符合要求的也可以称之为暴力算法。
枚举结构循环判断语句。
应用场合
在竞赛中并不是所有问题都可以使用枚举算法来解决事实上只有少数只有当问题的所有解的个数不太多时并在我们题目中可以接受的时间内得到问题的解才可以使用枚举。
枚举法的优缺点
枚举法的优点
由于枚举算法一般是现实生活中问题的“直译”因此比较直观易于理解
由于枚举算法建立在考察大量状态、甚至是穷举所有状态的基础上所以算法的正确性比较容易证明。
枚举法的缺点:
枚举算法的效率取决于枚举状态的数量以及单个状态枚举的代价因此效率比较低。
直译”枚举直接根据题意设定枚举对象、范围和约束条件。
算法复杂度是指算法在编写成可执行程序后运行时所需要的资源资源包括时间资源和内存资源。通常我们用时间复杂度和空间复杂度来描述算法所需要的时间资源和内存资源。
时间复杂度
时间复杂度表示程序运行占用时间的多少是评估算法效率的重要指标。一般表示为关于n的某个函数。其中n往往对应输入数据的规模用T(n)表示。
若有某个辅助函数f(n)存在一个正常数c使得f(n)×cT(n) 恒成立。记作T(n)O(f(n))称O(f(n))为算法的渐进时间复杂度简称时间复杂度。
时间复杂度常用大O符号表述不包括这个函数的低阶项和首项系数。
例如如果一个算法对于任何大小为n必须比n0大的输入它至多需要5n33n的时间运行完毕那么它的渐进时间复杂度是O(n3)。
我们知道常数项对函数的增长速度影响并不大所以当 T(n)cc为一个常数的时候我们说这个算法的时间复杂度为O(1)。如果 T(n) 不等于一个常数项时直接将常数项省略。比如cout hello world endl;
就是O(1)的。
一个函数中最高次项对函数的影响是最大所以在计算时间复杂度时刻直接忽略其他较低次项。
比如T(n)n3n21则对应的时间复杂度为O(n3)。
综合起来如果一个算法的执行次数是T(n)那么只保留最高次项同时忽略最高项的系数后得到函数f(n)此时算法的时间复杂度就是O(f(n))。在第二节中将介绍如何分析时间复杂度。
按数量级递增排列常见的时间复杂度有
常数阶O(1)对数阶O(log2n)以2为底n的对数下同线性阶O(n) 线性对数阶O(nlog2n平方阶O(n2)立方阶O(n3)...k次方阶O(nk)指数阶O(2n)。随着问题规模n的不断增大上述时间复杂度不断增大算法的执行效率越低。时间复杂度也是我们在做题时首先就要考虑的问题。
从运行效率来看 别名 效率从高到低 多项式复杂度 常数阶 O(1 多项式复杂度 对数阶 O(log(log(n))) 多项式复杂度 对数阶 O(log(n)) 多项式复杂度 对数阶 O((logn)2) 多项式复杂度 O(n−−√)O(n) 多项式复杂度 O(n2/3logn) 多项式复杂度 线性阶 O(n) 多项式复杂度 O(nlog(n)) 多项式复杂度 平方阶 O(n2) 多项式复杂度 立方阶 O(n3) 多项式复杂度 O(nk) 指数复杂度 斐波那契 O(Fib(n)) 指数复杂度 指数阶 O(2n 指数复杂度 指数阶 O(3n 指数复杂度 指数阶 O(n!) 指数复杂度 指数阶 O(nn)
注意log2nlog210×log10n 所以O(log2n)O(log10n)所以在谈论对数复杂度的算法时我们忽略是以2为底还是以10为底统称为O(log(n)) 。
对于所有复杂度为O(nk)的算法不论k有多大我们都称其为多项式时间的算法。所以O(nklogn)也是多项式时间的因为O(nklogn)≤O(nk1) 。
对于所有复杂度为O(kn) 的算法k1我们都可以称其为非多项式时间的算法经常会简化为指数级算法。
空间复杂度
空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。
比如 int a[100]; 所占用的内存空间大小 就是 100 ∗ 4 ∗ 8 bit 。一个长度为n的数组对应的空间复杂度为 O(n) 。
需要注意的是一段程序运行的时间复杂度不可能低于他的空间复杂度。
一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。当追求一个较好的时间复杂度时可能会使空间复杂度的性能变差即可能导致占用较多的存储空间。反之当追求一个较好的空间复杂度时可能会使时间复杂度的性能变差即可能导致占用较长的运行时间。
常见算法复杂度 复杂度 遍历 O(n) 冒牌排序 O(n2) 快速排序 O(nlog(n)) 全排列 O(n!)
复杂度分析基础
下面通过一些代码具体分析一下时间复杂度。
void aFunc(int n) {
for(int i 0; i n; i) { // 循环次数为 n cout Hello, World! endl; // 循环体时间复杂度为 O(1)
}
这段程序的循环运行次数为n次每次输出看作O(1)因此时间复杂度为O(n)。
void aFunc(int n) { for(int i 0; i n; i) { // 循环次数为 n for(int j 0; j n; j) { // 循环次数为 n cout Hello, World! endl; // 循环体时间复杂度为 O(1) } }
}
这段程序的外层循环运行次数为n次内层循环运行次数也是n次每次输出看作O(1)总共输出了n2行因此时间复杂度为O(n2) 。
void aFunc(int n) { // 第一部分时间复杂度为 O(n2) for(int i 0; i n; i) { for(int j 0; j n; j2) { cout Hello, World! endl; } } // 第二部分时间复杂度为 O(n) for(int j 0; j n; j) { cout Hello, World! endl; }
}
第一段程序会执行n2/2次第二段程序会执行n次共执行n2/2n 次因此时间复杂度为O(n2)。
void aFunc(int n) { for (int i 1; i * i n; i) cout Hello, World! endl;
}
当 in−−√in 时会退出循环。复杂度 O(n−−√)O(n) 。
void aFunc(int n) { for (int i 1; i n; i i) cout Hello, World! endl;
}
i的取值每次会翻倍因此程序只会执行log(n)复杂度为O(log(n))。对数复杂度的程序执行效率很高哪怕n1018也只会执60多次。
时间复杂度分析的基本策略从内向外分析从最深层开始分析。如果遇到函数调用要深入函数进行分析。
在学会了分析算法的复杂度后 我们要学会根据对应的数据范围设计出题目时间要求的时间复杂度。一般我们做题系统的评测机1s可运行百万级别 即每秒进行大约107次基础运算。设输入的数据量为n当n1000000时运行一段时间复杂度为O(n)的程序大约需要不到1s。而如果时间复杂度为O(n2)。则可能需要运行几天。 时间复杂度分析
复杂度分析进阶
void aFunc(int n) { for (int i 2; i n; i * i) cout Hello, World! endl;
}
这个ii×i函数的增长是很快的复杂度为O(log(log(n)))。在 n21024时也只会执行10 次左右。
void aFunc(int n) { for (int i 1; i n; i) { for (int j 1; j i; j j) cout Hello, World! endl; }
}
外层循环n次内层循环log(i)次因此总共循环的次数是
log(1)log(2)log(3)....log(n)∑i1nlog(i)
那么这个复杂度究竟是多少呢我们来进行一下推导
nlog(n)≥∑i1nlog(i)≥∑in/2
将所有log(i)换为log(n)所以有nlog(n)≥∑ni1log(i)。
去掉∑ni2log(i) 中小于 n/2的项所以有∑ni1log(i)≥∑nin/2log(i)把所有∑nin/2log(i)(i)中的i都换成 n/2所以有∑in/2nlog(i)≥(n/2)log(n/2)
有了这几个式子的比较我们看第1个式子对应的复杂度是O(nlog(n))最后一个式子对应的复杂度也是O(nlog(n))因此 ∑ni1log(i)∑i1nlog(i) 对应的复杂度是O(nlog(n))。
void aFunc(int n) { for (int i 1; i n; ii) { for (int j 1; j i; j) cout Hello, World! endl; }
}
外层循环共log(n)次内层每次循环到i。这个看起来似乎和上面的问题很像。但还需要仔细分析。我们先看n为2的幂的情况。总共循环的次数为
因此这个程序的复杂度为O(n)。下面的程序也是O(n)的。 空间换时间
在介绍复杂度的概念时曾讲过当追求一个较好的时间复杂度时可能会使空间复杂度的性能变差即可能导致占用较多的存储空间。很多时候优化时间复杂度的方法都是基于空间换时间的方法。
常用的空间换时间方法
在计算中有些数值会反复被用到如果每次都重新计算则会影响算法效率。我们可以通过一些手段提前处理好这些计算结果在计算过程中直接调用已经算出的部分。 方法 数组前缀和 O(1)求区间和 矩阵前缀和 容斥O(1) 求子矩阵和 质数表 加快分解质因数等等 打表 预先处理好需要重复计算的值
前缀和优化
给一个长度为n的数组有m次询问每一次询问区间[l,r]的和。最简单的做法是每一次询问都用for循环遍历数组[l,r]求一次和。这样复杂度是O(m×n) 。
我们可以预先处理一个数组 presum presum[i]就是[0,i] 的区间和 那么每当询问一个区间[l,r]时 答案就是presum[r]−presum[l−1]。可以在O(1)时间得到答案。
总的复杂度就是O(mn) 。例如
原数组为{1,5,9,4,3,3} 。
前缀和数组为{0,1,6,15,19,22,25} 。
除了前缀和常用的其实还有后缀和、前缀积、后缀积。核心思想都是经典的预处理思想。通过预处理将O(n×m)的复杂度降到O(nm)只是额外的使用了O(n)的空间这就是空间换时间的思想。
前缀和的逆运算是差分与差分相关的内容暂时不展开。
ST表
RMQRange Maximum Query问题是指对于长度为n的数列A回答若干询问Q(A,i,j)(i,jn)返回数列A中下标在(i−j) 里的最大值。RMQRMQ 问题是指求区间最值的问题。
RMQ问题有多种解决方式不同方法的复杂度不尽相同。这里只讲解最简单的 STST 表的方法。
XOR的特性
XOR运算具有一些独特的性质满足
交换律a xor bb xor a。结合律(a xor b)xor ca xor (b xor c)实际应用中我们还可以将 XOR其看作不进位的二进制加法。
尺取法
概念 尺取法也常被称为双指针是很常用的一种优化算法。通常是对数组保存一对下标即所选取的区间的左右端点然后根据实际情况不断地推进区间左右端点以得出答案。尺取法比直接暴力枚举区间效率高很多。
这么说可能有些抽象我们来举一个具体的例子。
在一个有序数组a 里所有数都大于0我希望为每个ai找到最小的ai×2 的数。
这里需要注意一个点就是数组a是有序的这是能够适用尺取法的前提。
对于a0我们可以从a1开始暴力找到第一个符合条件的ai对于a1我们就没有必要从a2开始找了因为a1a0所以-
2a12a0ai所以我们可以从ai 开始找即可以此类推直到处理完an−1。
这个算法的复杂度怎么分析呢左端点从a0变换为a1右端点也许直接从ai变为an。左端点走一步右端点走多少步并不确定最坏情况下要走O(n)步那么会不会这是一个最坏情况下O(n2)的算法呢
这时我们需要从总量上进行分析我们可以想象区间的左端点从0−(n−1)右端点也是从0−(n−1)并且不会向回走因此总的复杂度为O(n) 。
提到有序我们会联想到之前学习过的二分查找对于上面这个问题应用二分查找也是可以的。但我们来计算一下复杂度二分查找单次的复杂度为O(log(n))共需要执行n次因此总的复杂度为O(nlog(n))而运用尺取法复杂度优化为O(n)。
适用条件
尺取法通常适用于具备单调性的情况比如上面例子中a为有序数组所以右端点可以一直向右移动。如果没有这个条件则无法适用尺取法。这时我们可以先对a排序然后再使用尺取法。
谈到单调性我们容易联想到二分。二分在查找具体一个元素时可以达到O(log(n))的复杂度但如果处理 n个数则总的复杂度会变为O(nlog(n))这时如果可以使用尺取法可以将总的复杂度降为O(n) 。 贪心算法
贪心算法是指在对问题求解时总是做出在当前看来是最好的选择。也就是说不从整体最优上加以考虑他所做出的是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解关键是贪心策略的选择选择的贪心策略必须具备无后效性即某个状态以前的过程不会影响以后的状态只与当前状态有关。举例来说用2468组成最大的4位数。我们很自然的会想到8642因为在选择千位的数字时我们只需要考虑让这一位最大而后面的不论如何选都不会影响这一位的选择因此我们会选择8后面的处理也是一样。
贪心算法进阶
贪心的适用条件
贪心算法在对问题求解时总是做出在当前看来是最好的选择。也就是说不从整体最优上加以考虑他所做出的是在某种意义上的局部最优解。因此利用贪心算法来求最优解一定要满足当前最优即整体最优这个条件。
