最新军队文职-计算机类计算机类-数据结构与算法知识点总结

精品文档

增或递减）排列。

5. 索引顺序表查找又称分块查找。分块查找：块内无序、块间有序、如何分块效率最高 6. 动态查找表：二叉排序树查找：二叉排序树的生成

二叉排序树(二叉查找树)：或者是一颗空树。或者如下1若它的左子树不空，则左子树上所有的结点的值均小于他的根结点的值。2若右子树不空，则右子树所有结点的值均大于她得根结点的值。3 左右子树也分别为二叉排序树。

7. 哈希表：哈希函数构造：直接定址法、除留余数法、平方取中法，随机数法， 数字分析法

冲突解决方法：开放定址法、拉链法、公共溢出区法 七、 排序 1.插入类排序：

·直接插入排序

每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。 ·折半插入排序 ·希尔排序

基本思想：先将整个待排序记录序列分成为若干个子序列分别进行直接插入排序，待整个序列中的记录 基本有序 时在对全体序列进行一次直接插入排序，子序列的构成不是简单的逐段分割，而是将像个某个增量的记录组成一个子序列。 2.交换类排序

·起泡排序

也称冒泡法，每相邻两个记录关键字比大小,大的记录往下沉（也可以小的往上浮）。每一遍把最后一个下沉的位置记下，下一遍只需检查比较到此为止；到所有记录都不发生下沉时，整个过程结束（每交换一次，记录减少一个反序数）。 ·快速排序

在当前无序区R[1..H]中任取一个数据元素作为比较的\基准\不妨记为X)，用此基准将当前无序区划分为左右两个较小的无序区：R[1..I-1]和R[I+1..H]，且左边的无序子区中数据元素均小于等于基准元素，右边的无序子区中数据元素均大于等于基准元素，而基准X则位于最终排序的位置上，即R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H)，当R[1..I-1]和R[I+1..H]均非空时，分别对它们进行上述的划分过程，直至所有无序子区中的数据元素均已排序为止。 3.选择类排序

·简单选择排序

每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 ·堆排序

堆排序是一树形选择排序，在排序过程中，将R[1..N]看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。 4.归并类排序 ·二路归并排序

精品文档

精品文档

5.基数类排序

·基数排序

主要特点不需要进行关键字间的比较。 多关键字排序：

最高为优先（MSD法）从主关键字开始排序，再从次高位排序，一次类推，最后将所有子序列依次连接在一起成为一个有序序列。

最低位优先（LSD法）从最次位关键字开始排序，在对高一位的进行排序，直到成为一个有序序列。

排序方法 直接插入排序 快速排序 归并排序 简单选择排序 堆排序 基数排序 稳定性 稳定 不稳定 稳定 稳定 不稳定 稳定 平均时间 O（n*n） O（nlbn） O(nlbn) O（n*n） O（nlbn） 最坏情况 O（n*n） O（n*n） O（nlbn） O（n*n） O（nlbn） 辅助存储 O（1） O（lbn） O（n） O（1） O(1) O（rd） O（d（n+rd）） O（d（n+rd）） ? 选取排序方法需要考虑的因素： (1) 待排序的元素数目n； (2) 元素本身信息量的大小； (3) 关键字的结构及其分布情况；

(4) 语言工具的条件，辅助空间的大小等。 ? 小结：

(1) 若n较小(n <= 50)，则可以采用直接插入排序或直接选择排序。由于直接插入排序所需的记录移动操作较直接选择排序多，因而当记录本身信息量较大时，用直接选择排序较好。 (2) 若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。

(3) 若n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序。 快速排序是目前基于比较的内部排序法中被认为是最好的方法。

(4) 在基于比较排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程，由此可以证明：当文件的n个关键字随机分布时，任何借助于\比较\的排序算法，至少需要O(nlog2n)的时间。

算法分析知识点总结

算法概述

1、算法的五个性质：有穷性、确定性、能行性、输入、输出。 2、算法的复杂性取决于：（1）求解问题的规模（N）,（2）具体的输入数据（I），（3）算法本身的设计（A），C=F(N,I,A)。

3、算法的时间复杂度的上界记号O，

下界记号Ω(记为f(N) = Ω(g(N))。 即算法的实际运行时间至少需要g(n)的某个常数倍时间)， 同阶记号Θ：f(N)= Θ(g(N))表示f(N)和g(N)同阶 。

即算法的实际运行时间大约为g(n)的某个常数倍时间。 低阶记号o：f(N)=o(g(N))表示f(N)比g(N)低阶。 精品文档

精品文档

多项式算法时间：

O(1)

约定logn表示以2为底的对数。指数时间算法时间： O(2n)

4、常用算法的设计技术：分治法、动态规划法、贪心法、回溯法和分支界限法。 5、常用的几种数据结构：线性表、树、图。 6、算法:是指解决某一问题的运算序列

递归与分治

1、递归算法的思想：将对较大规模的对象的操作归结为对较小规模的对象实施同样的操作。 递归的时间复杂性可归结为递归方程：

其中，a是子问题的个数，b是递减的步长， ~表示递减方式，D(n)是合成子问题的开销。 递归元的递减方式~有两种：1、减法，即n – b，的形式。2、除法，即n / b，的形式。 2、递减方式为减法 设D(n)为常数，则有T(n) = O(an)。

(这里都是针对递减方式为除法的哦)D(n)为常数c：这时，T(n) = O(np)。 D(n)为线形函数cn：

D(n)为幂函数nx：

考虑下列递归方程：T(1) = 1 ⑴T(n) = 4T(n/2) +n ⑵ T(n) = 4T(n/2) +n2 ⑶ T(n) = 4T(n/2) +n3

解：方程中均为a = 4，b = 2，其齐次解为n2。 对⑴，∵ a > b1 (D(n) = n) ∴ T(n) = O(n2)； 对⑵，∵ a = b2 (D(n) = n2)∴ T(n) = O(n2log n)； 对⑶，∵ a < b3 (D(n) = n3)∴ T(n) = O(n3)；

证明一个算法的正确性需要证明两点：1、算法的部分正确性。2、算法的终止性。 3、汉诺塔问题：

void Hanoi(int n, int Fr, int To, int As) { 精品文档

精品文档

if (n > 0) {

Hanoi(n–1, A, C, B); Move(A, B);

Hanoi(n–1, C, B, A)} }

4、二分查找代码

精品文档