|
算法：算法是计算或者解决问题的步骤 算法运行时间：可以使用“步数”来描述运行时间。“1步”就是计算的基本单位。通过测试“计算从开始到结束总共执行了多少步”来求得算法的运行时间。 以排列整数顺序为例： 试着从理论层面求出选择排序的运行时间。选择排序的步骤如下： ① 从数列中寻找最小值 ② 将最小值和数列最左边的数字进行交换，排序结束。回到① 如果数列中有n个数字，那么①中“寻找最小值”的步骤只需确认n个数字即可。这里，将“确认1个数字的大小”作为操作的基本单位，需要的时间设为Tc，那么步骤①的运行时间就是n×Tc。 接下来，把“对两个数字进行交换”也作为操作的基本单位，需要的时间设为Ts。那么，①和②总共重复n次，每经过“1轮”，需要查找的数字就减少1个，因此总的运行时间如下。
运行时间的表示方法： 求得了运行时间，但这个结果还可以简化。Tc和Ts都是基本单位，与输入无关。会根据输入变化而变化的只有数列的长度n，所以接下来考虑n变大的情况。n越大，上式中的n2也就越大，其他部分就相对变小了。也就是说，对式子影响最大的是n2。所以，我们删掉其他部分，将结果表示成：
这就表示算法的运行时间与n的平方成正比。O这个符号的意思是“忽略重要项以外的内容”，读音同Order。O（n2）的含义就是“算法的运行时间最长也就是n2的常数倍”。 数据结构：数据存储于内存时，决定了数据顺序和位置关系的便是“数据结构” 链表：链表是数据结构之一，其中的数据呈线性排列。在链表中，数据的添加和删除都比较容易，而数据的访问比较耗费时间。 链表的概念图：
Blue、Yellow、Red这3个字符串作为数据被存储于链表中。这里，每个数据都有1个指针，它指向下一个数据的存储地址。（链表的数据一般是分散存储于数据中，无须存在连续的u空间中） 因为数据是分散的，故，若想访问数据，只能从第一个开始，顺着指针指向一一往下访问（顺序访问），如图中，想要访问Red，就一定会从Blue开始访问。 如果想要添加数据，只需改变添加位置前后的指针指向即可。(比如在Blue和Yellow之间添加Green) ①首先将Blue的指针指向Green ②再将Green的指针指向Red
删除数据时：（比如删除Yellow） ①将Green的指针直接指向Red
虽然Yellow本身还存储在内存中，但是不管从哪里都无法访问这个数据，所以也就没有特意去删除它的必要了。今后需要用到Yellow所在的存储空间时，只要用新数据覆盖掉就可以了. 对链表操作所需的运行时间：将链表中的数据量记为n。访问数据时，需要从链表头部开始访问查找（线性查找），如果目标数据在链表最后，则所需时间为O(n)。添加数据和删除数据与链表数据量无关，故为O(1)。 扩展链表： ①循环链表：循环链表没有头和尾的概念。想要保存数量固定的最新数据时通常会使用。
双向链表：设定指针为两个，并且分别让它们指向前后数据，这就是“双向链表”。（可从前往后和从后往前遍历数据，相对于单向链表更为方便）。 但是双向链表存在两个缺点: ①指针数的增加会导致存储空间需求增加 ②添加和删除数据时，需要改变更多指针的指向
数组：是数据呈线性排列的一种数据结构。在数组中，访问数据十分简单，但是添加和删除数据比较耗费时间。 数组的概念图：
数组按顺序存储在连续的空间内，故每个数据的内存地址（在内存上的位置）可以通过数组下标算出，可以直接访问目标数据（随机访问）。
如果我们想要访问Red。如果使用指针就只能从头开始查找，但在数组中，只需要指定a[2]，便能直接访问Red。但如果想在任意位置上添加或者删除数据，数组的操作就要比链表复杂很多。（比如将Green添加到第二个位置上） ①在数组末尾确保有需要增加的空间 ②将想要添加数据位置之后的数据一个个往后移一个空间 ③将数据放入
这样就完成了数据的添加操作。 若先删除数据，比如Green，则： ①删除目标数据Green ②将目标数据之后的数据依次往前移一个空间 ③删除最后数据之后多余的空间
对数组操作所需的运行时间：将数组中的数据量记为n。访问数据时为随机访问，故运行时间为恒定的O(1)。删除或者添加数据时，与数组数据量有关（需要往前或者往后移动目标位置之后的数据），故运行时间为O(n)。
总：在数组和链表中，数据都是呈线性排列。在链表中访问数据比较复杂，添加和删除数据比较简单；而在数组中，访问数据较为简单，添加和删除数据较为复杂。
栈：栈也是呈线性排列的数据结构，但在这种数据结构中，我们只能访问最新添加的数据，是一种“后进先出(LIFO)”的结构。 栈的概念图：
入栈：（添加数据）
出栈：（删除数据）
与链表和数组一样，栈的数据也是线性排列，但在栈中，添加和删除数据只能在一端进行，访问数据也只能访问到顶端的数据。想要访问中间的数据时，就必须通过出栈操作将目标数据移到栈顶。栈只能在一端操作这一点看起来似乎十分不方便，但若只需访问最新数据，使用起来就很方便。 队列：队列中的数据也呈线性排列。与栈有些相似，但队列中添加和删除数据的操作分别是在两端进行的。在队列中，最先进去的数据最先被取出来，是一种“先进先出(FIFO)"的结构。 队列的概念图：
入队：（添加数据）
出队：（删除数据）
在队列中取出（删除）数据时，是从最下面，也就是最早入队的数据开始。 与栈类似，队列中可以操作数据的位置也有一定的限制。队列中，数据的添加和删除在两端进行，队列不能直接访问最新和中间的数据，必须通过出队操作将目标数据变成首位后才能访问。 哈希表：哈希表存储的是由键(key)和值(value)组成的数据，使用哈希表可以使数据的查询效率得到显著提升。（一般来说，可以把键当成数据的标识符，把值当作数据的内容，键值不可重复） 如图，若用数组的方式存储数据，这里键是人名，值为对应的性别。
这里数据量越多，线性查找耗费的时间就越长。故由于数据的查询较为耗时，所以此处并不适用使用数组来存储数据。若使用哈希表（如图）： 使用哈希函数（Hash）计算人名的键，也就是字符串的哈希值，再将哈希值对数组长度求余。 字符串"Joe"为4928，4928 mod 5=3; 字符串"Sue"为7291，7291 mod 5=1; 字符串"Dan"为1539，1539 mod 5=4; 字符串"Nell"为6276，6276 mod 5=1(若发生位置冲突，则在可对应位置处使用链表); 字符串"Ally"为9143，9143 mod 5=3; 字符串"Bob"为5728，5728 mod 5=3;
此时，若想查询“Dan”的性别，只需通过算出“Dan”的哈希值，再对5求余便能找到所存储的位置，若发现相应位置存储的不是"Dan"，则需要对该位置的链表进行线性查找，即可。
可知道"Dan"的性别为男，查找"Ally"也是如此。
"Ally"性别为女。 在哈希表中，我们可以利用哈希函数快速访问到数组中的目标数据。如果发生哈希冲突，就使用“链表”进行存储。这样一来，不论数据量为多少，都可以灵活应对。如果数组空间太小，使用哈希表的时候就容易发生冲突，线性查找使用的频率也会更高。反过来，若数组的空间太大，就会出现很多空闲的空间位置，造成内存的浪费。因此，给数组设定合适得空间非常重要。 补充说明： 在存储数据中，如果发生冲突，可以利用链表再已有数据的后面插入新数据来解决冲突。这种方法被称为“链地址”法。 除“链地址法”以外，还有几种解决冲突的方法。其中，应用较为广泛的是“开放地址法”。这种方法是指当冲突发生时，立刻计算出一个候补地址（数组上的位置）并将数据存进去。如果仍然有冲突，便继续计算下一个候补地址，直到有空位置为止。可以通过多次使用哈希函数或者“线性探测法”等方法计算候补地址。 堆：堆是一种图的树形结构，被用于实现“优先队列（priority queues）”。“优先队列”是一种数据结构，可自由添加数据，但取出数据时要从最小值开始按顺序取出。在堆的树形结构中，各个顶点被称为“结点(node)”，数据就存储在这些结点中。 堆的示例如下：
结点内的数字就是存储的数据。堆中的每个结点最多有两个子节点。树的形状取决于数据的个数。另外，结点的排列顺序为从上到下，同一行里则为从左到右。 在堆中存储时必须遵守这样一规则：子节点必定大于父节点。因此，最小值被存储在顶端的根节点中。往堆中添加数据时，为了遵守这条规则，一般会把新数据放在最下面一行靠左的位置。但下面一行里没有多余的空间时，就再往下另起一行，把数据加在这一行的最左端。 添加数据：（添加数据5） ①把数据放在最下面一行靠左的位置
②如果父结点大于子结点，则不符合上文提到的规则，因此需要交换父子结点的位置
③若存在②情况，交换父子结点。重复这样的操作直到数据都符合规则，不再需要交换为止
此时，往堆中添加数据的操作就完成了。 删除数据：（取出数据） 从堆中取出数据时，取出的是最上面的数据。这样，堆就能始终保持最上面的数据最小。
但由于最上面的数据被取出，因此堆的结构也需要重新调整。 ①（按照从上到下，从左到右）的排列顺序，将最后的数据（此处为6）移动到最顶端
②如果子节点的数字小于父结点，就将父节点与其左右两个子节点中较小的一个进行交换。
③重复②操作，知道数据都符合规则，不再需要交换为止。
这样就完成了从堆中取出数据的操作。 堆中最顶端的数据始终最小，所以无论数据量有多少，取出最小值的时间复杂度都为O（1）。另外，因为取出数据后需要将最后的数据移到最顶端，然后一边比较它与子结点数据的大小，一边往下移动，所以取出数据需要的运行时间和树的高度成正比。假设数据量为n，根据堆的形状特点可知树的高度为log2n，那么重构树的时间复杂度便为O（logn）。添加数据也一样。在堆的最后添加数据后，数据会一边比较它与父结点数据的大小，一边往上移动，直到满足堆的条件为止，所以添加数据需要的运行时间与树的高度成正比，也是O（logn）。 如果需要频繁地从管理的数据中取出最小值，那么使用堆来操作会非常方便。如狄克斯特拉算法，每一步都需要从候补顶点中选择距离起点最近的那个顶点。此时，在顶点的选择上就可以用到堆。 二叉查找树：（又叫二叉搜索数或二叉排序树）是一种给数据结构，采用了图的树形结构，数据存储在二叉查找树的各个结点中。 二叉查找树的示例如下：
节点中的数字便是存储的数据。此处以不存在相同数字为前提进行说明。 二叉查找树有两个性质。 ①每个结点的值均大于其左子树上任意一个结点的值。比如结点9大于其左子树上的3和8。 ②每个结点的值均小于其右子树上任意一个结点的值。比如结点15小于其右子树上的23、17、28。 故二叉查找树的最小结点要从顶端开始，往其左下的末端寻找。反过来，二叉查找树的最大顶点要从顶端开始，往其右下的末端寻找。 添加数据：（添加数据1和4） ①从二叉查找树的顶端结点开始寻找添加数字的位置 ②若比结点大则往右移，小则往左移
删除结点： ①若需要删除的结点没有子节点，直接删除该结点（如删除结点28）
②如果需要删除的结点只有一个子节点，则先删除目标结点，再将子节点移动到被删除结点上的位置（删除结点8）
③如果需要删除的结点有两个子节点，则先删除目标结点，然后再被删除结点的左子树中寻找最大结点，最后将最大结点移动到被删除结点位置上。如果需要移动的结点还有子节点，就递归执行前面的操作。（删除结点9）
删除9的时候，我们将“左子树中的最大结点”移动到了删除结点的位置上，但是根据二叉查找树的性质可知，移动“右子树中的最小结点”也没有问题 查找结点：（查找12） ①首先与二叉查找树的顶端结点开始查找，比顶端结点大则往右子树移动，继续重复操作，反之，则往左子树移动，继续重复操作。
这样就找到了结点12。 可以把二叉查找树当作是二分查找思想的体现。因为它具有前面二叉查找树的那两个性质，所以在查找数据的时候或者寻找适合添加数据的位置时，只要将其和现有数据比较结果就可以知道往哪边移动。 比较次数取决于树的高度。所以如果结点数目为n，而且树的形状又较为均衡的话，比较大小和移动的次数最多就是log2n。因此，时间复杂度为O（logn）。但是，如果树的形状朝单向纵向延申，书就会变得很高，此时时间复杂度也就变成了O(n）。 补充说明： 有很多以二叉查找树为基础拓展的数据结构，比如“平衡二叉查找树”。这种数据结构可以修正状况不均衡的树，让其始终保持均衡状态，以提高查找效率。 另外，虽然文中介绍的二叉查找树中一个节点最多有两个子节点，但我们可以把子节点数拓展为m（m为预先设置好的常熟）。像这种直接点数可以自由设定，并且形状均衡的树便是B树。 |
|
|
