第六周作业
1. 势能分析法说明删除时数组大小$n \leq \frac14 c$才将数组容量缩小为原来的$\frac12$并把数据复制过去的均摊复杂度也为$O(1)$
定义$\Phi(n,c)=\begin{cases}2n-c & n\geq\frac{1}{2}c\\ \frac{1}{2}c-n&n<\frac{1}{2}c\end{cases}$
当$n>\frac{1}{4}c$时，不会缩容，开销为$1$，$\Delta\Phi=(2(n-1)-c) - (2n-c)=-2$或$=(\frac12 c-(n-1))-(\frac12c-n)=1$，$c_i=1+\Delta\Phi=O(1)$
当$n\leq\frac{1}{4}c$时，缩容的拷贝开销为$n$，$\Delta\Phi=\left(\frac12\cdot \frac12c-\left( n-1 \right) \right) - \left(\frac12c-n\right)=1-\frac14c$，$c_i=n+\Delta\Phi\leq1=O(1)$
得证
2. 用势能分析法说明2-3树插入和删除操作的时间复杂度都是平摊$O(\log{n})$
定义$\Phi=h$
插入
当不需要分裂节点时，只需要$O(\log{n})$地查找节点位置，$O(1)$插入即可，$\Delta\Phi=0$，$c_i=O(\log{n})$
需要分裂节点时，
父节点为2节点时，直接把子节点中间大小的元素与父节点合并，最大最小元素变成父节点的另外两个子节点。需要$O(\log{n})$查找节点位置，$O(1)$插入，$\Delta\Phi=0$，$c_i=O(\log{n})$。
父节点为3节点时，将子节点子节点中间大小的元素与父节点合并，最大最小元素变成父节点的另外两个子节点。这样父节点有3个元素、4个子节点，需要继续向上传进行分裂，四个子节点两个归左边两个归右边。需要$O(\log{n})$查找节点位置，$O(1)$插入，$\Delta\Phi=0$，$c_i=O(\log{n})$。
没有父节点时，需要新建一个节点用来存放子节点的中间值。需要$O(\log{n})$查找节点位置，$O(1)$插入，$\Delta\Phi=1$，$c_i=1+O(\log{n})=O(\log{n})$。
所以均摊的时间复杂度为$O(\log{n})$
删除
删除的元素不为叶子时，找前驱，和父节点元素交换，然后删除。查找开销$O(\log{n})$，$\Delta\Phi=0$，$c_i=O(\log{n})$
删除的元素位于3节点的叶子时，直接删除即可。查找开销$O(\log{n})$，$\Delta\Phi=0$，$c_i=O(\log{n})$
删除的元素位于2节点的叶子时，
若兄弟节点为3节点，那么删除位置换成它的前驱/后继（原来在父节点上），再把换下来元素的前驱/后继放在父节点上。查找开销$O(\log{n})$，$\Delta\Phi=0$，$c_i=O(\log{n})$
若兄弟节点为2节点、父节点为3节点，那么向父节点借，并与兄弟节点结合，最后父节点从 3-节点变成了 2-节点。查找开销$O(\log{n})$，$\Delta\Phi=0$，$c_i=O(\log{n})$
若父节点和兄弟节点均为2节点，那么首先让父节点和兄弟节点合并。此时原来的父节点内值为空，为填补这个空节点，我们要再对父节点执行一次删除操作（仅为调整结构）。查找开销$O(\log{n})$，$\Delta\Phi=0$，$c_i=O(\log{n})$
所以均摊的时间复杂度为$O(\log{n})$
3. 设计一个队列，支持入队enqueue，出队dequeue和查询最小值find_min，每个操作都是平摊$O(1)$，并用势能分析法分析复杂度。
两个队列，main和min，main就是正常队列，min递增，用来存可能的最小元素
定义势能函数$\Phi=main.size()$
入队$x$
往main里面push，如果$x$比min队列的头还小，那就一直把比$x$还小的值pop出去（它们不会再进入main队列了），再将$x$ push进min队列。
$\Delta\Phi=-\Delta(main.size())$，$c_i=1+\Delta(main.size())+\Delta\Phi=1=O(1)$
出队
将main的队首pop掉，如果出队的元素等于 min 的第一个元素，则也将 min 的第一个元素出队。
$\Delta\Phi=-1$，$c_i=1+1+\Delta\Phi=1=O(1)$
查找min
min队列的队头就是，$\Delta\Phi=0$，$c_i=O(1)$
4. 设计一个数据结构，动态维护一个大小$m$为的集合$S$，支持插入一个元素insert，和删除最小的$\lceil \frac{n}2\rceil$个元素remove_bottom_half，每个操作都是平摊$O(1)$，并用势能分析法分析复杂度。
动态数组中存储元素的值。定义势能函数$\Phi=6n$
插入
添加到数组末尾里即可，$\Delta\Phi=4$，$c_i=1+\Delta\Phi=7=O(1)$
删除
$O(n)$扫描整个数组的有效元素出来，$O(n)$计算出中位数（找第k小），再$O(n)$扫描所有小于中位数的值，打上删除标记即可。不过需要定期缩容。
$\Delta\Phi=6(n-\lceil \frac n2\rceil)-6n=-3n$，$c_i=3n+\Delta\Phi=0=O(1)$
5. $n$个数排成一行，其中第$i$个是整数$a_i$，初始均为$0$。 执行$m$次assign(l, r, x)操作。每次对于所有$l\leq i\leq r$，将$a_i$赋值为$x$，每次操作的消耗定义为区间里不同$a_i$的个数。
(1) 使用势能分析法说明$m$次操作的消耗最多是$3m$。
定义势能函数$\Phi=\text{序列内相邻两元素不相同的个数}$，如$a=[1,2,3,2,2,1]$则$\Phi=4$
每次assign操作时，会将区间内设为同一个值（区间内相邻元素不同的个数减少或不变），可能在区间边界新增和相邻元素不同的个数，但至多为$2$，因此$\Delta\Phi\leq2$
令$k_i\geq1$表示单次操作时区间内不同元素的个数，显然在操作结束之后这$k_i$个不同的元素就变成同一个了，也就是影响$\Delta\Phi$的$r-l+2$（暂不考虑数列边界）个数中有$r-l$个数在操作后变为同一个数了，至多新增$2$个不同的数（边界上）。所以$\Delta\Phi+k_i\leq3$，那么$c_i=k_i+\Delta\Phi\leq3$
$m$次操作的总代价为$\sum\limits_{i=1}^{m}{c_i}\leq3m$
(2) 说明任意小于$3$的常数都不成立。
最坏情况为$3$且能取到，所以不能比$3$还小。
