排序算法
平均时间复杂度
最好情况
最坏情况
空间复杂度
稳定性
冒泡排序
O(n2)
O(n)
O(n2)
O(1)
稳定
选择排序
O(n2)
O(n2)
O(n2)
O(1)
不稳定
插入排序
O(n2)
O(n)
O(n2)
O(1)
稳定
希尔排序
O(nl...
总结一些在网上看到的关于KMP算法的简单理解,目前我的理解还很初步,很多东西还似懂非懂,目前先贴下来,期待以后慢慢懂。
KMP算法的基本原理
假设字符串S=BBC ABCDAB ABCDABCDABDE,搜索词P=ABCDABD。那么我们...
一、判断题
1-1若用平方探测法解决冲突,则插入新元素时,若散列表容量为质数,插入就一定可以成功。(2分)
F
1-2对N个不同的数据采用冒泡排序进行从大到小的排序,当元素基本有序时交换元素次数肯定最多。(2分)
F...
第十一讲:散列查找
11.1 散列表
11.1.1 散列的基本思路
编译处理时,设计变量及属性的管理:
(1)插入:新变量定义。
(2)查找:变量的引用。
编译处理中对变量管理:动态查找问题。
利用查找树进行变量管理,...
第十讲:排序(下)
10.1 快速排序
10.1.1 算法概述
策略:分而治之。
下面举个例子,假如一组数为13/81/92/43/65/31/57/26/75/0,我们对其进行排序。那么首先选择出一个主元,这里我们选择为65,那么将这组数的...
第九节:排序(上)
9.1 概述
对于之后应用到的一些说明:
(1)void X_Sort(ElementType A[], int N) X为排序名称。
①大多数情况下,为了简单起见,讨论从小到大的整数排序。
②默认N为正整数。
③只讨论基于比较...
第八讲:图(下)
8.1 最小生成树问题
8.1.1 最小生成树(Minimum Spanning Tree)
如图1所示。
图1
它是一棵树:无回路;|V|个顶点一定有|V|-1条边;
它是生成树:包含全部顶点;|V|-1条边都在图里。在图...
第七节:最短路径问题
7.1 概述
最短路径问题的抽象:
在网络中,求两个不同顶点之间的所有路径中,边的权值之和最小的那一条路径。这条路径就是两点之间的最短路径。第一个顶点称为源点,最后一个顶点为终点。
...
第六节:图(上)
6.1 图
1.关于图
图表示的是“多对多”的关系。它包含:
(1)一组顶点:通常用V(Vertex)表示顶点集合。
(2)一组边:通常用E(Edge)表示边的集合,表示顶点与顶点的关系:
①边是顶点对:(v,w...