算法

线性表 线性表(linear list)是种非常简单的结构。一个线性表等价于一个集合与该集合所有元素的一个排序，可写成$[a,b,c,…]$的形式，方括号中的内容既表示线性表中的全部元素，也表示这些元素的排序。对于线性表中任意前后相邻的$x_i$与$x_{i+1}$元素，通常称$x_i$的后继为$x_{i+1}$，$x_{i+1}$的前驱为$x_i$，首个元素的前驱为空，最后一个元素的后继为空。需注意到线性表本身是个逻辑概念，其不限制也不依赖于具体实现，就类似于集合这样的概念，在讨论算法时经常会遇到这种类型的概念。 在算法领域人们更关心线性表的实现，因为线性表本身十分简答。 实际的计算机硬件基本都采用相同的“内存模型”，其包括由确定的$K$个连续整数构成的$K$个内存地址，每个地址都存储相同规模的数据。读取内存的流程大致是先提供内存地址给内存，一段时间后内存返回该地址中的数据，写入内存的流程大致是同时提供地址和数据给内存，一段时间后内存完成写入。在这种“内存模型”下，线性表的实现方案通常是数组或链表，这两种方案都有各自的优缺点。当然如果不采用这种“内存模型”，也有一定的可能会用其他方案来实现线性表。… 阅读全文

栈(Stack)栈这种结构强调的是栈运算，实现了如下3种运算的结构就是栈： 1) $push(x)$：存入$x$元素(也称为压栈)； 2) $pop()$：删除最后一次存入的元素并返回该元素(也称为弹栈)； 3) $top()$：返回最后一次存入的元素(也称为栈顶，所以写作top)； 直观上栈像狭长的储物箱，只有一面开口，只能看到最顶上的物品，取最里面的物品时要自顶向下的先拿出所有其他物品。这3种运算使栈中的元素在逻辑上也蕴含着前驱后继关系，所以栈也是线性表。但栈不必像数组和链表那样，必须提供查看任意元素、在任意元素间插入、删除任意元素等各种运算，所以直观上栈并不像一张“表”，而像是有3个运算的“黑箱”，所以栈也被称为操作受限的线性表。当然如果在链表或数组的基础上实现栈运算的话，那也可以作为栈。栈作为后进先出(LIFO,… 阅读全文

直接寻址表(Direct Address Table)数组是把所有元素按顺序存储在连续内存地址中的，如果单个元素需要的内存地址数越多，数组整体需要的内存地址数就要成倍增长。显然同样大小的连续内存比不连续内存更“稀缺”，因为即使有足够的内存，也不代表有足够的连续内存。那么为更合理的使用内存，在元素数量多且单个元素很大的场景下就不应直接使用大数组存储，而是应该考虑使用链表，但如果对按索引访问的性能有高的要求，就需要结合数组和链表的特点构造一种新的称为直接寻址表的结构。直接寻址表本身是个数组，但元素不存入数组，而是存入不连续的其他内存区域，数组中存储的是元素的内存地址。 直接寻址表的各个位置称为槽(slot)，其允许索引不连续(索引1有元素、索引2没元素、索引3又有元素……)，所以把索引改称为关键字(key)。当元素不大时，也允许不存地址，而是依然存元素本身。所以数组可看作直接寻址表的特例，很多时候甚至不区分这两个概念，因为直接寻址表仅多了1次按地址找元素的步骤，和数组的代价是没有区别的。直接寻址表还有些其他好处，数组创建时必须确定每个元素占用的固定大小。直接寻址表就自由的多，由于其存储的只是地址，所以元素的大小可以不同。事实上很多程序语言中“基于数组”的数据类型更接近直接寻址表而不是数组，比如Python的list。… 阅读全文

摊还分析(Amortized Analysis) 通常算法分析的“目标问题”都是给定1个规模为$n$的数据结构和1个算法，分析该算法关于$n$的代价并表示为$O(f(n))$。如果在此基础上继续分析“在该数据结构连续执行$k$次该算法”的问题，用乘法可得$O(kf(N))$，其中$N$是$k$次中最大的$n$。由于$O$是上界所以该结论完全正确，但可能不够“精确”(离确界不够近)。因为没考虑到每次算法执行后，数据结构本身的变化。如果考虑到，则可能得到小于$O(kf(N))$的界，并且其更能反映出该场景下的真实代价。 举例说明上述观点，假设有个“包含$popAll$运算”的栈，其除了能$O(1)$完成$push,pop,top$，还支持$popAll$运算，其实现是“循环$pop$直到栈顶为空”，如果$popAll$执行前栈中有$n$个元素，$popAll$的代价就是$O(n)$。然后带入场景“这个栈是某算法的一部分，该算法会多次调用这个栈的$push,pop,popAll$，由于这个算法很复杂，不能确定每次都调用什么运算，也不能确定每次调用前栈的元素数。只知道算法开始时栈是空的”。由于不知道元素数，$popAll$的$O(n)$代价就不精确了，但我们很想衡量这个栈在该算法中的性能表现，所以构造下面这个需要做算法分析的“目标问题”：… 阅读全文