Book Notes · Weiss · Analysis

数据结构与算法分析
实现对照

C++ / Java 版目录略有出入，下面按「同一 ADT、不同实现、界怎么变」读。摊还与若干平衡树细节标超纲。

01表、栈、树

Weiss 的习惯是先写接口，再给向量与链表两套实现，强迫你比较代价。

接口→向量 O(1) 下标/链表改链→谁付定位的账

向量按位插入要搬元素，O(n)。单链表定位 O(n)，已有前驱后改链 O(1)。双链表在已知结点上插删都可以 O(1) 改链。

BST 查找、插入、删除都是 O(h)。平均对数只在随机插入这类分布下谈期望；AVL 用旋转把 h 钉在 Θ(log n)。

进阶 / 超纲伸展树的摊还界、AA 树、Treap 的随机优先级证明，408 不要求默写。

分离链接与开放定址对照。同一散列/探查方式与均匀假设下，α 越大期望探查越长；开放定址还要求 α<1。

本站二次探查约定 h+i²，不算 −i²。删除用墓碑：直接清空会截断探查链。

易错：不要把「平均 O(1)」写成无条件结论。最坏可以全撞，O(n)。

二叉堆：上滤下滤。建堆从最后一个非叶往根下调，总共 O(n)。堆排序最坏也是 O(n log n)，默认实现通常不稳。

直接插入最好 O(n)、稳定。快排平均必须写「随机输入/随机枢轴」前提。归并稳定、额外 O(n)。

进阶 / 超纲左式堆、斜堆、配对堆的摊还分析不进 408 简答。

先声明邻接表还是矩阵，再写 BFS/DFS 的 O(V+E) 或 O(V²)。Dijkstra 非负权；矩阵实现常见 O(V²)。Floyd O(V³)，允许负权禁负环。

Bellman-Ford 标准单源版本只能检出从源点可达的负权环。

自底向上：大部分结点高度很小，高度求和是常数倍 n。逐个插入才是 O(n log n)。

看他握的是不是前驱（或双向指针）。单链表只握待删结点，默认不是 O(1)。

标超纲。统考要的是最坏/平均/最好三条曲线和前提，不是势能函数。