算法的基本概念

算法与数据结构

算法

算法：解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作

算法的特性：输入、输出 有穷性、确定性和可行性

• 输入输出：具有零个或多个输入、至少有一个或多个输出
• 有穷性：算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成
• 确定性：算法的每一步骤都具有确定的含义，不会出现二义性
• 可行性：算法的每一步都必须是可行的，也就是说，每一步都能够通过执行有限次数完成

算法设计的要求：

• 正确性：算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案。算法的"正确"大体分为以下四个层次：

  1. 算法程序没有语法错误
  2. 算法程序对于合法的输入数据能够产生满足要求的输出结果
  3. 算法程序对于非法的输入数据能够得出满足规格说明的结果
  4. 算法程序对于精心选择的，甚至刁难的测试数据都有满足要求的输出结果

• 可读性：算法设计的另一目的是为了便于阅读、理解和交流

• 健壮性：当输入数据不合法时，算法也能做出相关处理，不是产生异常或莫名
  其妙的结果
  设计算法应该尽量满足时间效率高和存储量低的需求

算法效率的度量方法：

• 事后统计方法：这种方法主要是通过设计好的测试程序和数据，利用计算机计时器对不同算法编制的程序的运行时间进行比较，从而确定算法效率的高低
• 事前分析估算方法：在计算机程序编制前，依据统计方法对算法进行估算

一个用高级程序语言编写的程序在计算机上运行时所消耗的时间取决于下列因素：

1. 算法采用的策略、方法（算法好坏的根本）
2. 编译产生的代码质量（软件）
3. 问题的输入规模
4. 机器执行指令的速度（硬件）

抛开与计算机硬件、软件有关的因素，一个程序的运行时间依赖：算法的好坏和问题的输入规模

分析程序的运行时间时：重要的是把程序看成是独立于程序设计语言的算法或一系列步骤

判断一个算法的效率时：函数中的常数和其他次要项常常可以忽略，而更应该关注主项(最高阶项)的阶数

函数的渐近增长：给定两个函数 f(n)和g(n)，如果存在一个整数使得对于所
有的n>N, f(n)总是比g(n)大，那么就说f(n)的增长渐近快于g(n)。于是可以得出一个结论，判断一个算法好不好，只通过少量的数据是不能做出准确判断的，如果可以对比算法的关键执行次数函数的渐近增长性，基本就可以分析出某个算法，随着n的变大，它会越来越优于另一算法，或者越来越差于另一算法

算法的时间复杂度：
在进行算法分析时，语句总的执行次数T(n)是关子问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，记作:T(n)=O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和
f(n)的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。 其中f( n) 是问题规模n的某个函数

推导大O阶：

1. 用常数1取代运行时间中的所有加法常数
2. 在修改后的运行次数函数中，只保留最高阶项
3. 如果最高阶项存在且不是1，则去除与这个项相乘的常数
   得到的结果就是大O阶

常见的时间复杂度：

常见的时间复杂度所耗费的时间从小到大依次是：
0(1) < O(log2n) < O(n) < O(nlog2n) < 0(n2) < 0(n3) <...< 0(2") < O(n!) < O(n")

其中Ο(log2n )、Ο(n)、 Ο(nlog2n )、Ο(n2)和Ο(n3)称为多项式时间，而Ο( 2n)和Ο(n!)称为指数时间。计算机科学家普遍认为前者（即多项式时间复杂度的算法）是有效算法，把这类问题称为P（Polynomial,多项式）类问题，而把后者（即指数时间复杂度的算法）称为NP（Non-Deterministic Polynomial,非确定多项式）问题

算法的空间复杂度： 通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作: S(n)= O( f(n)) ，其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数

查找

查找表(Search Table)是由同一类型的数据元素〈或记录)构成的集合：

关键字(Key)： 数据元素中某个数据项的值，又称为键值，用它可以标识一个数据元素。也可以标识一个记录的某个数据项(字段)，称为关键码 （①和②所示）
主关键字(Primary Key)：若此关键字可以唯一地标识一个记录，则称此关键字为主关键字（③和④所示）
次关键字(Secondary Key)： 对于那些可以识别多个数据元素(或记录)的关键字，称为次关键字（⑤所示）
查找( Searching )：就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）

若表中存在这样的一个记录，则称查找是成功的，此时查找的结果给出整个记录的信息，或指示该记录在查找表中的位置；若表中不存在关键字等于给定值的记录，则称查找不成功，此时查找的结果可给
出一个"空"记录或u空"指针。

查找表按照操作方式来分有两大种：静态查找表和动态查找表

静态查找表(Static Search Table)：只作查找操作的查找表。主要操作有:

1. 查询某个"特定的"数据元素是否在查找表中
2. 检索某个"特定的"数据元索和各种属性

动态查找表(Dynamic Search Table)：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。动态查找表的操作就是两个:

1. 查找时插入数据元素
2. 查找时删除数据元素

为了提高查找的效率，我们需要专门为查找操作设置数据结构，这种面向查找操作的数据结构称为查找结构。从逻辑上来说，查找所基于的数据结构是集合，集合中的记录之间没有本质关系。可是要想获得较高的查找性能，就不能不改变数据元素之间的关系，在存储时可以将查找集合组织成表、树等结构。

1、顺序表查找
顺序查找( Sequential Search)：又叫线性查找，是最基本的查找技术，它的查找过程是：从表中第一个（或最后一个）记录开始，逐个进行关键之与给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；如果知道最后一个记录，其关键字与给定值比较都不等时，则表中没有所查找的记录，查找不成功。

2、有序表查找
①折半查找：又称二分查找。它的前提是线性表中的记录必须是关键码有序的（通常是从小到大有序），线性表必须采用顺序存储。折半查找的基本思想是:在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功;若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所有查找区域元记录，查找失败为止

②插值查找：是根据要查找的关键字key与查找表中最大最小记录的关键字比较后的查找方法，其核心就在于插值的计算公式：$mid = low + \frac{key-a[low]}{a[high]-a[low]} (high - low)$

③斐波那契查找：利用黄金分割原理来实现

3、线性索引查找
数据结构的最终目的是提高数据的处理速度，索引是为了加快查找速度而设计的一种数据结构。索引就是把一个关键字与它对应的记录相关联的过程，一个索引由若干个索引项构成，每个索引项至少应包含关键字和其对应的记录在存储器中的位置等信息。索引技术是组织大型数据库以及磁盘文件的一种重要技术。

索引按照结构可以分为：线性索引、树形索引和多级索引

线性索引：就是将索引项集合组织为线性结构，也称为索引表 （稠密索引、分块索引和倒排索引）

①稠密索引：是指在线性索引中，将数据集中的每个记录对应一个索引项。对于稠密索引这个索引表来说，索引项一定是按照关键码有序的排列。
优点：索引项有序也就意味着，我们要查找关键字时，可以用到折半、插值、斐被那契等有序查找算法，大大提高了效率
缺点：如果数据集非常大，比如上亿，那也就意味着索引也得同样的数据集长度规模，对于内存有限的计算机来说，可能就需要反复去访问磁盘，查找性能反而大大下降了

②分块索引：对于分块有序的数据集，将每块对应一个索引项，这种索引方法叫做分块索引
分块有序，是把数据集的记录分成了若干块，并且这些块需要满足两个条件：

1. 块内无序，即每个块内不要求有序
2. 块间有序，例如第二块的所有记录的关键字均要大于第一块中的所以记录的关键字

分块索引的索引项结构分为三个数据项：

1. 最大关键码，存储每一块中最大的关键字
2. 存储了每块的记录数，以便于循环使用
3. 用于指向块首数据元素的指针
   

③倒排索引：

表示单词以及单词在哪些文章中出现，这张单词表就是索引表
索引项的通用结构：
• 次关键码（上面的"英文单词"）
• 记录号表（上面的"文章编号"）
其中记录号表存储具有相同次关键字的所有记录的记录号(可以是指向记录的指针或者是该记录的主关键字) ，这样的索引方法就是倒排索引(invened index)

4、二叉排序树

二叉排序树（Binary Sort Tree）：又称为二叉查找树，它或者是一颗空树，或者是具有下列性质的二叉树:

• 若它的左子树不空，则左子树上所有的节点的值均小于根节点值
• 若它的右子树不空，则右子树所有的节点的值均大于根节点值
• 它的左、右子树也分别为二叉排序树

从二叉排序树的定义也可以知道，它前提是二叉树，然后它采用了递归的定义方法，再者，它的结点间满足一定的次序关系，左子树结点一定比其双亲结点小，右子树结点一定比其双亲结点大。

构造一棵二叉排序树的目的，其实并不是为了排序，而是为了提高查找和插入删除关键字的速度。不管怎么说，在一个有序数据集上的查找，速度总是要快于无序的数据集的，而二叉排序树这种非线性的结构，也有利于插入和删除的实现。

二叉排序树是以链接的方式存储，保持了链接存储结构在执行插入或删除操作时不用移动元素的优点，只要找到合适的插入和删除位置后，仅需修改链接指针即可。插入删除的时间性能比较好。而对于二叉排序树的查找，走的就是从根结点到要查找的结点的路径，其比较次数等于给定值的结点在二叉排序树的层数。极端情况，最少为1次，即根结点就是要找的结点，最多也不会超过树的深度。也就是说，二叉排序树的查找性能取决于二叉排序树的形状（但二叉排序树的形状是不确定的）

5、平衡二叉树（AVL树）
平衡二叉树： (Self-Balancing Binary Search Tree 或 Height-Balanced Binary Search Tree)，是一种二叉排序树（一种高度平衡的二叉排序树），其中每一个节点的左子树和右子树的高度差至多等于1

平衡因子BF(Balance Factor)：将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF，那么平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。

最小不平衡子树：距离插入节点最近的，且平衡因子的绝对值大于1的节点为根的子树，称为最小不平衡子树

当新插入结点37时，距离它最近的平衡因子绝对值超过1的结点是58(即它的左子树高度2减去右子树高度0），所以从58开始以下的子树为最小不平衡子树

6、多路查找树（B树）

一个结点只能存储一个元素，在元素非常多的时候，就使得要么树的度非常大(结点拥有子树的个数的最大值)，要么树的高度非常大，甚至两者都必须足够大才行。这就使得内存存取外存次数非常多，这显然成了时间效率上的瓶颈，要打破每一个结点只存储一个元素的限制，为此引入了多路查找树的概念。

多路查找树(muitl-way search tree)：其每一个结点的孩子数可以多于两个，且每一个结点处可以存储多个元素 （每一个结点可以存储多少个元素，以及它的孩子数的多少是非常关键的）

①2-3树：2-3树的每一个结点都具有两个孩子（称它为2结点)或三个孩子（称它为3结点)

• 一个2结点包含一个元素和两个孩子(或没有孩子)，且与二叉排序树类似，左子树包含的元素小于该元素，右子树包含的元素大于该元素。不过，与二叉排序树不同的是，2结点要么没有孩子，要有就有两个，不能只有一个孩子
• 一个3结点包含一小一大两个元素和三个孩子(或没有孩子)，一个3结点要么没有孩子，要么具有3个孩子。如果某个3结点有孩子的话，左子树包含小于较小元素的元素，右子树包含大于较大元素的元素，中间子树包含介于两元素之间的元素
  

②2-3-4树：是2-3树的概念扩展，包括了4结点的使用。一个4结点包含小中大三个元素和四个孩子（或没有孩子)

• 如果某个4结点有孩子的话，左子树包含小于最小元素的元素；第二子树包含大于最小元素，小于第二元素的元素;第三子树包含大于第二元素，小于最大元素的元素；右子树包含大于最大元素的元素。

③B树（B-Tree）：是一种平衡的多路查找树，2-3树和2-3-4树都是B树的特例。结点最大的孩子数目称为B树的阶（order），因此，2-3树是3阶B树，2-3-4树是4阶B树
一个m阶的B树具有如下属性：

• 如果根结点不是叶结点，则其至少有两棵子树
• 每一个非根的分支结点都有k-l个元素和k个孩子，其中[m/2]<=k<=m。每一个叶子结点n都有k-l个元素，其中[m/2]<=k<=m。
• 所有叶子结点都位于同一层次
• 所有分支结点包含下列信息数据(n，A0，K1，A1，K2，A2，...,Kn，An)，其中: Ki(i=1,2,...,n)为关键字，且Ki

④B+树（B-Tree）：
B+树是应文件系统所需而出的一种树的变形树，注意严格意义上讲，它其实已经不是树了。在B树中每一个元素在该树中只出现一次，有可能在叶子结点上，也有可能在分支结点上。而在 B+树中，出现在分支结点中的元素会被当作它们在该分支结点位置的中序后继者(叶子结点)中再次列出。另外，每一个叶子结点都会保存一个指向后一叶子结点的指针。

（灰色关键字即是根结点中的关键字在叶子结点再次列出，并且所有叶子结点都链接在一起）

一棵m阶的B+树和m阶的B树的差异在于：

• 有n棵子树的结点中包含有n个关键字
• 所有的叶子结点包含全部关键字的信息，及指向含这些关键字记录的指针，叶子结点本身依关键字的大小自小而大顺序链接
• 所有分支结点可以看成是索引，结点中仅含有其子树中的最大(或最小)关键字

7、散列表查找（哈希表）
散列技术：是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f(key)。查找时，根据这个确定的对应关系找到给定值key的映射f(key)，若查找集合中存在这个记录，则必定在f(key)的位置上（散列技术最适合的求解问题是查找与给定值相等的记录）
把这种对应关系f称为散列函数，又称为哈希(Hash)函数。按这个思想，采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表(Hash table)。关键字对应的记录存储位置称为散列地址。

散列表查找步骤：

1. 在存储时，通过散列函数计算记录的散列地址，并按此散列地址存储该记录
2. 当查找记录时，我们通过同样的散列函数计算记录的散列地址，按此散列地址访问该记录

散列技术既是一种存储方法，也是一种查找方法。然而它与线性表、树、图等结构不同的是，前面几种结构，数据元素之间都存在某种逻辑关系，可以用连线图示表示出来，而散列技术的记录之间不存在什么逻辑关系，它只与关键字有关联。因此，散列主要是面向查找的存储结构。

在理想的情况下，每一个关键字，通过散列函数计算出来的地址都是不一样的，可现实中，这只是一个理想。我们时常会碰到两个关键字key1!=key2，但是却有f(key1)=f(key2)，这种现象称为冲突(collision)，并把key1和key2称为这个散列函数的同义词(synonym)

散列函数的构造方法：

• 直接地址法
• 数字分析法
• 平方取中发
• 折叠法
• 除留余数法：此方法为最常用的构造散列函数方法。对于散列表长为m的散列函数公式为：f(key) = key mod p(p<=m)
• 随机数法

应该视不同的情况采用不同的散列函数。根据一些考虑的因素来提供参考：

• 计算散列地址所需的时间
• 关键字的长度
• 散列袤的大小
• 关键字的分布情况
• 记录查找的频率。综合这些因素，才能决策选择哪种散到函数吏合适

处理散列冲突的方法：

• 开放定址法：开放定址法就是一旦发生了冲突就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。解决冲突的开放定址法称为线性探测法
• 再散列函数法
• 链地址法
• 公共溢出区法

散列表查找性能：
如果无冲突，O(1)
查找平均长度取决于：
- 散列函数是否均匀
- 处理冲突的方法
- 散列表的装填因子
装填因子=填入表中的记录个数/散列表长度。（表示散列表的装满的程度）当填入表中的记录越多，装填因子越大，产生冲突可能性越大。通常将散列表的空间设置的比查找集合大，牺牲空间换时间。

排序

假设含有n个记录的序列为{rl,r2,...,rn}，其相应的关键字分别为{k1,k2,...,kn}，需确定1, 2, ..., n的一种排列P1,P2,...,Pn，使其相应的关键字满足kp1<=kp2<=...<=kpn(非递减或非递增)关系，即使得序列成为一个按关键字有序的序列{rp1,rp2,...rpn}， 这样的操作就称为排序

排序的稳定性：
假设ki=kj(1<=i<=n,1<=j<=n,i!=j)，且在排序前的序列中ri领先于rj(即i

内排序和外排序：
根据在排序过程中待排序的记录是否全部被放置在内存中， 排序分为：内排序和外排序
内排序是在排序整个过程中，待排序的所有记录全部被就置在内存中。外排序是由于排序的记录个数太多， 不能同时放置在内存，整个排序过程需要在内外存之间多次交换数据才能进行

对于内排序来说，排序算法的性能主要是受3个方面影响：
1. 时间性能（高效率的内排序算法应该是具有尽可能少的关键字比较次数和尽可能少的记录移动次数）
2. 辅助空间（辅助存储空间是除了存放待排序所占用的存储空间之外，执行算法所需要的其他存储空间）
3. 算法的复杂性（算法本身的复杂度，而不是指算法的时间复杂度）

根据排序过程中借助的主要操作，把内排序分为：插入排序、交换排序、选择排序和归并排序

时间复杂度对比：

维基百科所有排序算法：