数据结构

摊还分析(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)$代价就不精确了，但我们很想衡量这个栈在该算法中的性能表现，所以构造下面这个需要做算法分析的“目标问题”：… 阅读全文

反转数组 该问题是“给定一个数组，将其元素按从右到左重新排列，比如输入$[1,2,3]$，应该得到$[3,2,1]$。要求在原数组上反转，且只能占用常数额外空间”。这个问题可通过以中心为对称轴，从最外层开始反转，比如$[1,2,3,4,5]$，会先变成$[5,2,3,4,1]$，然后变成$[5,4,3,2,1]$，两轮即可完成。然后考虑问题的边界，当数组有奇数个元素，两索引最后会在中心元素处相遇，当数组有偶数个元素，两索引最后会出现右边小于左边的情况。所以当右边的索引小于等于左边的索引时就意味着算法结束。该算法的时间复杂度是$O(n)$，其中$n$为数组中元素的个数。具体程序实现如下。 Python def reverse(arr): i, j = 0, len(arr) - 1 while… 阅读全文

反转链表该问题是“给定链表(表头节点)，将链表逆序，要求原地完成(由原节点构成)且只占常数额外空间”。先考虑递归程序，思路是递归进入到链表尾，然后在每次递归退出时，让外层递归把当前节点原后继的$next$反过来指向当前节点。需注意最后一次递归结束后，其当前节点的$next$没有发生变化，所以要特别的将其指向空，那为了方便干脆在每轮递归结束前都加一步把当前节点的$next$指向空。然后是如何记录新表头，上述递归没有用到函数返回值，可以一层层返回新表头。 Python def f(node): if not node.next: return node newHead = f(node.next) node.next.next = node node.next = None return newHead 1234567 def… 阅读全文

栈的最小值 该问题是“实现一个空栈存储数值，其支持一般的$push,pop$，以及用于求当前栈中最小值的$min$运算，要求3个运算的时间复杂度都是$O(1)$”。问题要求找最小值的代价是$O(1)$，那只能在$push,pop$的过程中用额外空间维护一些关于最小值的信息。假设栈只有$push$运算，那只需1个额外变量就能记录栈中的最小值，但当存在$pop$运算时，如果最小值元素被$pop$了，那就只能遍历寻找新的最小值，代价就不再是$O(1)$。这里就需要注意到栈的一个性质，即“每次$pop$后栈会回到最后一次$push$前的状态”。这说明如果用一个结构顺序记录每次$push$后的“历史最小值”，那么$pop$后的最小值就是这个结构中的倒数第2条记录，然而倒数第一条记录因为$pop$结束已经没意义了，应从中删除，这又说明这个结构也很适合用栈实现。… 阅读全文

两个栈实现队列 该问题是“有2个空栈$s_1,s_2$，出入栈运算都是$O(1)$代价的，要求用这2个栈实现一个队列，出入队运算都是$O(1)$摊还代价的”。用2个栈实现队列的思路很简单，把一组元素入栈$s_1$再出栈入栈到$s_2$就能把$s_1$的栈底变成$s_2$的栈顶，进而就能实现队头的出队。这里具体来看如何实现，首先对于入队运算，直接入栈$s_1$即可，对于出队运算，当$s_2$为空时把$s_1$的元素全部出栈并依次入栈$s_2$，最后弹出$s_2$的栈顶作为队头出队。当$s_2$非空，直接弹出$s_2$的栈顶作为队头出队即可。 上述过程中，每个元素的入队都是1次$s_1$的入栈，出队都是3次的$s_1$出栈、$s_2$入栈、$s_2$出栈操作。对于$2n$次队列操作，最好的情况是发生$2n$次入队操作，最坏的情况是发生$n$次入队、$n$次出队，对于最坏的情况，也仅意味着发生了$4n$次栈操作。所以此时的总代价是$O(n)$，每次操作的摊还代价是$O(1)$。下面是具体程序实现。… 阅读全文

计数排序(Count Sort) 计数排序是最简单的基于哈希表的排序算法，常用的排序算法是比较排序，但基于哈希表的排序一般都属于非比较排序。这类排序算法的特点是牺牲空间来换取更低的时间复杂度，这个时间复杂度甚至低于比较排序的理论极限$O(n\lg n)$。但这类排序对输入的数有限制、并且可能会占用相当多的空间，所以应用并不如比较排序广。 计数排序要求输入的每个数都必须是整数，算法流程是先创建空哈希表，然后遍历输入找到最大值$max$和最小值$min$，再在哈希表中依次插入关键字$min, min+1,…,max$并让每个关键字关联一个值用来表示“关键字在输入中的个数”，所以值初始都为0。然后遍历输入并在哈希表统计各数的出现次数，最后根据$max$和$min$按\(min,… 阅读全文