常用算法复杂度速查表 - SegmentFault 思否

绪论

算法：是为了解决某类问题而规定的一个有限长的操作序列。

五个特性：有穷性、确定性、可行性、输入、输出

评价算法优劣的基本标准（4个）：

正确性、可读性、健壮性、高效性及低存储量

​ 常见的算法时间复杂度由小到大依次为：image-20220316143749407

img

常见时间复杂度

image-20220322201328442
image-20220322201337562

image-20220322201401167

image-20220322201522419

image-20220429151146516)、image-20220429151349939

栈和队列

前，中，后缀表达式

添加到第(N+1)个,移动平均：(0+1+2+……+N)/(N+1)=N/2

删除第N个,移动平均：[0+1+……+(N-1)]/N=(N-1)/2

环形队列

1、front：指向队列的第一个元素，即array[front]就是队列的第一个元素，front的初始值是0；

2、rear：指向队列的最后一个元素的后一个位置，空出一个空间做为约定（实际存储数据会比最大容量小1），rear的初始值是0；

3、maxSize：队列的最大容量；

4、队列满的条件是：（rear+1）%maxSize == front ；

5、队列为空的条件：rear == front；

6、队列中的有效数据个数：（rear + maxSize - front）% maxSize

数组和广义表

在这里插入图片描述

image-20220406173800225

image-20220324201019506

矩阵（稀疏矩阵）压缩存储（3种方式） (biancheng.net)

十字链表

这里写图片描述

串

子串长度：n(n+1)/2 + 1

树和二叉树

树的转换

image-20220325180611435

二叉树转换为树：

image-20220325180626855

森林转换为二叉树

image-20220325180705550

二叉树转换为森林

image-20220325180720205

二叉树的性质

image-20220325180202645

性质1：树中的结点数等于所有结点的度数加1

每个结点的度数分别对应结点的子结点，所有结点的度数为b，因此结点数n = b +根节点，即n = b + 1.

性质2：度为m的树中第i层上至多有m的i-1次方个结点(i>=1)

本性质采用数学归纳法进行证明：
1）当树为第一层时，第一层至多有m0=1个结点
2）当树为第i-1层时，由该性质值第i-1层至多有mi-2个结点
3）当树为第i层时，由于树的度为m，可知每个第i-1层的每个结点至多有m个子结点，因此第i层至多有mi-2*m=mi-1个结点。
因此性质得证。

性质3：高度为h的m叉树至多有(m^h-1)/(m-1)个结点

由性质2可知，度为m的数第i层至多有mi-1个结点，因此高度为h的m叉树至多有n = m0+m1+…+mh-1个结点，用等比数列公式求和，可以得到n= (mh-1)/(m-1).

性质4：具有n个结点的m叉树的最小高度为⌈logm(n(m-1)+1)⌉

性质4是由性质3逆推得到，由得到最小高度可知树的每一层都具有最多结点。由于高度为整数，且多余结点也是一层，因此树的高度需要向上取整。

其他总结

二叉树中n0=n2+1

满二叉树n，高度为 log2(n+1)

n节点，空指针域n+1

n节点，分支树，或所有节点度之和为n-1

哈夫曼树

哈夫曼树中单节点分支为0，m为叶子结点数，节点总数为 2m-1

哈夫曼树权值计算

结点的带权路径长度：结点到树根之间的路径长度与该结点上权的乘积

image-20220325185844619

线索二叉树

image-20220329195904314

image-20220329195959739、

image-20220329200326095

图

有向完全图：有n(n-1)条边的图，就是图中任意两点均有边相连的图。

完全图：有n(n-1)/2条边的图，就是图中任意两点均有边相连的图。

弧尾：边的始点称弧尾。

弧头：边的终点称弧头，即箭头的一端。

出度：顶点v的出度即是以该顶点为始点的边的数目。

入度：顶点v的入度即是以该顶点为终点的边的数目。

度：无向图中顶点的度就是关联于该顶点的边的数目。

强连通分量：有向图的极大强连通子图称为强连通分量。

强连通图：有向图中，若图中任意两个不同顶点都存在路径，则称该图为强连通图。

连通分量：无向图的极大连通子图称为它的连通分量。

图的遍历：从图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历。

生成树：生成树是连通图的极小连通子图。所谓极小是指：若在树中任意增加一条边，则将出现一个回路；若去掉一条边，将会使之变成非连通图。

生成树的权：生成树各边的权值总和称为生成树的权。

最小生成树：权最小的生成树称为最小生成树。

有向无环图：一个无环的有向图称做有向无环图。

AOV网络：用顶点表示活动，用有向边<Vi,Vj>表示活动Vi必须先于活动Vj进行，即用弧表示活动间的优先关系。这种有向图叫做顶点表示活动的AOV网络。

AOE网：AOE网是一个带权的有向无环图，其中，顶点表示事件，弧表示活动，权表示活动持续的时间。

关键路径：从源点到汇点的最长路径长度叫做关键路径。

关键活动：关键路径上的所有活动都是关键活动。

最短路径：即求两个顶点间长度最短的路径，但不是指路径上边数的总和，而是指路径上各边权值的总和。

存储结构

img

常见算法时间复杂度

DFS

深度优先搜索（Depth_Fisrst Search）遍历类似于树的先根遍历，是树的先根遍历的推广。

实质上是对每个顶点查找其邻接点的过程，其耗费的时间取决于所采用结构。

显然，这是一个递归的过程。为了在遍历过程中便于区分顶点是否已被访问，需附设访问标志数组visited[0:n-1], ，其初值为FALSE ，一旦某个顶点被访问，则其相应的分量置为TRUE。

从图的某一点v 出发，递归地进行深度优先遍历的过程如下：

1
2
3
4
5
6
7
void DFS(Graph G,int v )
{ /*从第v 个顶点出发递归地深度优先遍历图G*/
	visited[v]=TRUE;VisitFunc(v); /*访问第v 个顶点*/
	for(w=FisrAdjVex(G,v);w; w=NextAdjVex(G,v,w))
		if (!visited[w]) 
			DFS(G,w); /*对v 的尚未访问的邻接顶点w 递归调用DFS*/
}

邻接表表示时，查找所有顶点的邻接点所需时间为O(E)，访问顶点的邻接点所花时间为O（V）,此时，总的时间复杂度为O(V+E)。

邻接矩阵表示时，查找每个顶点的邻接点所需时间为O(V)，要查找整个矩阵，故总的时间度为O(V^2)。

v为图的顶点数，E为边数。

BFS

遍历顶点的每个相邻边的时间复杂度称为O(N)，其中N是相邻边的数量。因此，对于V个顶点，时间复杂度变为O(V*N)=
O(E)，其中E是图形中边的总数。由于是从Queue中删除顶点或向Queue中添加顶点O(1)，因此为什么将顶点添加到BFS的整体时间复杂度中O(V+E)。

图的基本术语

最小生成树算法Prim,Kruskal

Prim算法的时间复杂度为O(n^2)

Kruskal的算法复杂度为O(eloge)

image-20220326152812589

image-20220326152937138

image-20220326153042843

普里姆Prim

image-20220326153313684

image-20220326153941317

克鲁斯卡尔Kruskal

image-20220326153606844

image-20220326154033035

最短路径Dijkstra,Flody

image-20220326154215555

Dijkstra

​ 时间复杂度为：O(n^2)

image-20220326155346561

image-20220326155544368

Flody

拓扑排序AOV网

​ n个顶点，e条边的有向无环图过不排序时间复杂度为 O(n+e)

image-20220303143113175

image-20220303143023873

  1. 找到无入度的点
  2. 任选其中一点加入排序队列

关键路径AOE网

image-20220326152608882

活动余量为0则为关键

在这里插入图片描述

查找

时间复杂度

  1. 顺序查找法的平均查找长度为：(n+1)/2

image-20220410161254189

关于ASL(平均查找长度)的简单总结

B树

对于关键字为n，高度为h，阶数为m的B数，最小高度为：

image-20220315164829954

image-20220315165936276

image-20220311151158567

image-20220311153112186

B+树

image-20220311155504952

image-20220311155901265

二叉排序树BFS

image-20220315143446548

image-20220315143732507

二叉排序树删除节点的几种方法

1：删除节点左子树的最右边的元素替代之，相当于用前继节点替代

2：删除节点右子树的最左边的元素替代之，相当于用后继节点替代

以上两种都不改变中序遍历二叉树所得的顺序

3：设要删除的节点是B，节点B是节点A的左子树。删除节点B以后，令B的左子树为A的左子树，B的右子树加到B的左子树的最右边。

4：http://www.cppblog.com/guogangj/archive/2009/10/26/99502.html，假设要删除节点A，则（考虑节点A的左子树，找出左子树中最大的节点并与A替换，若此时A为叶子节点，则直接删除，否则重复括号内的过程）。

image-20220315150720753

二叉平衡树AVL

image-20220315151154407

image-20220503150212253

散列

二次探测

如何用二次探测法处理散列冲突

排序

排序算法

创建二叉排序树的时间复杂度是O(nlog2n)

image-20220308113351939

各种常用排序算法
类别 排序方法 时间复杂度 空间复杂度 稳定性 复杂性 特点
最好 平均 最坏 辅助存储 简单
插入排序 直接插入 O(N) O(N2) O(N2) O(1) 稳定 简单
希尔排序 O(N) O(N1.3) O(N2) O(1) 不稳定 复杂
选择排序 直接选择 O(N) O(N2) O(N2) O(1) 不稳定
堆排序 O(N*log2N) O(N*log2N) O(N*log2N) O(1) 不稳定 复杂
交换排序 冒泡排序 O(N) O(N2) O(N2) O(1) 稳定 简单 1、冒泡排序是一种用时间换空间的排序方法，n小时好2、最坏情况是把顺序的排列变成逆序，或者把逆序的数列变成顺序，最差时间复杂度O(N^2)只是表示其操作次数的数量级3、最好的情况是数据本来就有序，复杂度为O(n)
快速排序 O(N*log2N) O(N*log2N) O(N2) O(log2n)~O(n) 不稳定 复杂 1、n大时好，快速排序比较占用内存，内存随n的增大而增大，但却是效率高不稳定的排序算法。2、划分之后一边是一个，一边是n-1个，这种极端情况的时间复杂度就是O(N^2)3、最好的情况是每次都能均匀的划分序列，O(N*log2N)
归并排序 O(N*log2N) O(N*log2N) O(N*log2N) O(n) 稳定 复杂 1、n大时好，归并比较占用内存，内存随n的增大而增大，但却是效率高且稳定的排序算法。
基数排序 O(d(r+n)) O(d(r+n)) O(d(r+n)) O(rd+n) 稳定 复杂
注：r代表关键字基数，d代表长度，n代表关键字个数

image-20220312112056055

img

堆排序

image-20220314170311713

img

当下沉的子节点值想等时，往左边下沉

错题总结

下标运算

循环队列对头尾不熟悉，

数据结构的多种实现

查漏补缺

  • 排序算法
  • AVL树
  • 二叉树和森林转换
  • 根据遍历结果还原树
  • 多存储结构的实现
  • 哈夫曼树权值计算
  • 常见算法实现和时间复杂度
  • 图的一些概念
  • 有序链表倒置算法
  • AOE网
  • 图遍历
  • 概念知识
  • 查找算法实现细节
  • 折半查找插入
  • 树的兄弟链存储遍历
  • 前中后缀表达式
  • 算法分析
  • 十字链表
  • 排序算法的实现
  • 快速排序、堆排序、归并排序和基数排序实现细节
  • 拓扑排序细节
  • 简答题
  • 算法题
  • 链式基数排序
  • B树

错题总结

选择题

image-20220419171919318

image-20220419173614764

image-20220419173800940

image-20220419173900928

image-20220419182416393

image-20220419182436191

image-20220419182500767

image-20220419183224000

image-20220419183347050

image-20220419183508163

image-20220419183524997

image-20220419183820495

image-20220420154554738

image-20220423155734018

image-20220424151023382

image-20220427170851058

image-20220428152547920

image-20220429151747367

image-20220429152438882

image-20220430152535881

image-20220430152543162

image-20220430152526461

image-20220501151321133

image-20220501151201526

image-20220501151216649

image-20220501151310233

image-20220501153946878

image-20220501154128087

image-20220502143045905

image-20220502143115045

image-20220507183353878

image-20220503141814188

image-20220503153447157

image-20220503155007210

image-20220503170245692

image-20220504153636450

image-20220508143710735

image-20220510151230840

image-20220510164314683

判断题

image-20220420161514256

image-20220420161521022

image-20220420172714974

image-20220426210425048

image-20220426210529001

image-20220430161052722

image-20220508145542178

填空题

image-20220419175030402

image-20220419175057666

image-20220419175110388

image-20220419175353242

image-20220419180206090

image-20220419180634952

image-20220419183021218

image-20220420163912980

image-20220423153014808

image-20220423153104625

image-20220423160756011

image-20220424153445884

image-20220424161617533

image-20220424161652516

image-20220424161953062

image-20220425151817333

image-20220425152517224

image-20220425153544391)image-20220425154520963)image-20220425154620266

image-20220426205821295

image-20220426205827791

image-20220426211024450

image-20220426211309692

image-20220426211603514

image-20220430152559107

image-20220502141422559

image-20220508152649702

image-20220508152657694

image-20220509163553255

image-20220510154329258

大题

image-20220505155210139

image-20220510155053510

【一棵度为2的树和一棵二叉树有什么区别】

1、度不同

度为2的树要求每个节点最多只能有两棵子树，并且至少有一个节点有两棵子树。二叉树的要求是度不超过2，节点最多有两个叉，可以是1或者0。

在任意一棵二叉树中，叶子结点总是比度为2的结点多一个。

2、分支不同

度为2的树有两个分支，但分支没有左右之分；
一棵二叉树也有两个分支，但有左右之分，左右子树的次序不能随意颠倒。

3、次序不同

度为2的树从形式上看与二叉树很相似，但它的子树是无序的，而二叉树是有序的。即，在一般树中若某结点只有一个孩子，就无需区分其左右次序，而在二叉树中即使是一个孩子也有左右之分。

  1. image-20220323180455658

image-20220319170015052

image-20220331145111010

image-20220331151804815

image-20220425153024587

算法题总结

image-20220408170943155

image-20220410144553917

image-20220410144912197

、image-20220410144917819

image-20220410162632281

image-20220410162651135

image-20220411164317056

image-20220414154755866

image-20220419174928388

image-20220419183140950