标签：lfloor 摊还 leq 导论 平摊 算法 Theta 操作 代价

基本概念

摊还分析也称平摊分析，用于总体考虑分析问题，通过 \(n\) 次操作来计算平均代价。

与平均情况分析的区别：平摊分析不涉及到概率，保证其平摊性能是每个操作在最坏情况下具有的平均性能。

三种平摊分析技术：

聚合分析（Aggregate analysis）

先求出操作序列里所有操作 \(n\) 个的总代价上界 \(T(n)\)，则每个操作的平摊代价 \(T(n)/n\)

核算法（Accounting method）

对操作序列中的各操作进行收费，以支付操作作为实际代价。

先确定操作序列中各种操作的平摊代价（费用），对不同的操作收费可以不同

对有的操作超额收费：该操作实际成本低于该收费，余款作为预付存款存储在数据结构某些特殊对象上

对有的操作收费不足：该操作实际成本大于此收费，不足部分由特殊对象上的存款进行支付

势能法（Prepaid method）

与核算法类似之处是也须先确定每个操作的平摊成本（收费），对某些操作预先超额收费以补偿后续收费不足的操作

不同之处是存款是作为整个数据结构的“势能”加以维护，而不是将存款与数据结构中某些个体对象联系起来

聚合分析

栈操作

数据结构和操作

数据结构：栈 \(S\)，初始为空

操作：

• \(Push(S,x)\)：将 \(x\) 入栈，时间 \(O(1)\)
• \(Pop(S)\)：将栈顶元素出栈，时间 \(O(1)\)
• \(MultiPop(S,k)\)：弹出 \(min(|S|,k)\) 个对象，时间 \(O(min(|S|,k))\)

时间分析

聚合分析可以得到紧确界：因为一个对象入栈后至多被弹出一次，所以在非空栈上调用 \(Pop\) 的次数至多为 \(Push\) 的次数。

因此，当栈 \(S\) 为空时，\(Push\) 的次数至多为 \(O(n)\)，而 \(Pop\) 的次数至多为 \(O(n)\)。因为每个 \(Pop\) 和 \(Push\) 的实际代价均为 \(O(1)\)，所以对任意整数 \(n\)，操作序列长度为 \(n\) 时，总时间 \(T(n)=O(n)\)，三个操作的平摊代价均 \(O(n)/n=O(1)\)

二进制计算器

数据结构和操作

用 \(A[0,...,k-1]\) 表示二进制计算器，初始 \(A[i]=0,0\leq{i}\leq{k-1}\)

二进制数 \(X=\sum_{i=0}^{k-1}A[i]2^i\)，其中低位在 \(A[0]\)

加 1 操作：

void increment(int[] A) {
	// 最高位进位舍弃，即X=2^k时，A中全是0
  int i = 0;
  while(i < length(A) && A[i] == 1) {
  	// 从低位到高位进行扫描，如果当前位为1，将其翻转为0，进位向前，直到找到一个值为0的位或所有位都扫描完
    A[i] = 0;
    i++;
  }
  if(i < length(A)) {
  	A[i] = 1;
  }
}

时间分析

8 bit 二进制计算机从 0 变化到 16 （通过加一操作）对应的操作所需要的步骤如下：

\(n\) 次增量操作中，并非每次所有位都会发生变化。上图就可以表明：无论 \(n\) 为多少，总翻转次数 \(<2n\)，即总代价为 \(O(n)\)

当位 \(i\leq{\lfloor{lgn}\rfloor}\) 时：

• \(A[0]\)，每调用 1 次翻转 1 次，共 \(n\) 次翻转
• \(A[1]\)，每调用 2 次翻转 1 次，共 \(\lfloor{n/2}\rfloor\) 次翻转
• \(A[2]\)，每调用 4 次翻转 1 次，共 \(\lfloor{n/4}\rfloor\) 次翻转
• \(\cdot\cdot\cdot\)
• \(A[i]\)，每调用 \(2^i\) 次翻转 1 次，共 \(\lfloor{n/2^i}\rfloor\) 次翻转

当位 \(i>{\lfloor{lgn}\rfloor}\) 时：因为 \(n\) 的二进制最多有 \(\lfloor{lgn}\rfloor+1\) 位，所以 \(A[i]\) 在 \(n\) 次增量操作中，没有翻转。

综上：\(\sum_{i=0}^{\lfloor{lgn}\rfloor}\lfloor{\frac{n}{2^i}}\rfloor<n\sum_{i=0}^{\infty}\frac{1}{2^i}=2n\)

操作序列总代价为 \(O(n)\)，每次操作的平摊成本为 \(O(n)/n=O(1)\)

核算法

栈操作

平摊代价

	实际代价	平摊代价
\(Push\)	1	2
\(Pop\)	1	0
\(MultiPop\)	\(min(k,s)\)	0

平摊代价的正确性：证明任何时候栈中元素的总存款大于0

\(Push\)：当一个元素入栈时，支付 2 元钱，1 元用作该操作的实际成本，另外 1 元用作该元素之后出栈时所需的成本，因为一个元素只会出入栈一次。

\(Pop,MultiPop\)：平摊成本为 0 元，因为要出栈的每个元素都有 1 元的存款。

时间分析

每个操作平摊成本是 \(O(1)\)，\(n\) 个由 \(Push\)，\(Pop\) 和 \(Multipop\) 组成的操作序列总平摊成本是 \(O(2n)\)，因此总实际成本为 \(O(2n)\)。

二进制计算器

平摊代价

	实际代价	平摊代价
置位 \(0\rightarrow1\)	1	2
复位 \(1\rightarrow0\)	1	0

平摊代价的正确性：证明任何时候各个位总存款大于0

当某位被置 1 时，2 元收费中 1 元用于支付实际成本，另 1 元存在该位上，则计数器中，值为 1 的位上均有 1 元存款。当某位复位时，用该位上 1 元存款来支付复位的实际成本。

时间分析

一次操作最多只有一次置位，则其平摊成本 \(\leq{2}\)，\(n\) 次增量操作的总平摊成本 \(2n\in{O((n)}\)

势能法

基本概念

• 数据结构：\(D\)，初态记为 \(D_0\)
• 操作：\(n\) 个，可变
• \(i^{th}\) 操作 \(OP_i\) 的结果：\(D_{i-1}\rightarrow{D_i}\)
• 势函数 \(\Theta(D_i)\)：将每个 \(D_i\) 映射为一个实数，函数值看作势能
• \(OP_i\) 的实际成本为 \(C_i\)
• \(OP_i\) 的平摊成本为 \(\hat{C}_i=C_i+\Theta(D_i)-\Theta(D_{i-1})\)

操作的平摊代价由两部分构成：实际成本 \(C_i\) 和势差：

\[\begin{cases} \Theta(D_i)-\Theta(D_{i-1})>0,\hat{C}_i超额收费,势能\uparrow \\ \Theta(D_i)-\Theta(D_{i-1})<0,\hat{C}_i收费不足,势能\downarrow \\ \Theta(D_i)-\Theta(D_{i-1})=0,\hat{C}_i=C_i \end{cases} \]

总的平摊代价及势函数的正确性

\[\begin{align} \sum_{i=1}^n\hat{C}_i &=\sum_{i=1}^n(C_i+\Theta(D_i)-\Theta(D_{i-1})) \\ &=\sum_{i=1}^nC_i+\Theta(D_n)-\Theta(D_0) \end{align} \]

\(n\) 个操作后，势差为：序列最终的势能和最初的势能之差。

\(\forall{i}\in{I},\Theta(D_0)\leq{\Theta(D_i)}\)，通常定义 \(\Theta(D_0)=0\)，则 \(\forall{i}\in{I},\Theta(D_i)\geq{0}\)

栈操作

势函数 \(\Theta\)：栈中对象数目 \(|S|=s\)

• 初始：设 \(D_0\) 表示空栈，\(Φ(D_0)=0\)
• 任意时刻，栈中对象数非负，\(\Theta(D_i)\geq{0}\)

栈操作的平摊成本：

• \(Push\)：
  • 势差：\(\Theta(D_i)-\Theta(D_{i-1})=(s+1)-s=1\)
  • 平摊成本：\(\hat{C}_i=C_i+\Theta(D_i)-\Theta(D_{i-1})=1+1=2\)
• \(Pop\)：
  • 势差：\(\Theta(D_i)-\Theta(D_{i-1})=(s-1)-s=-1\)
  • 平摊成本：\(\hat{C}_i=C_i+\Theta(D_i)-\Theta(D_{i-1})=1-1=0\)
• \(Multipop(S,k)\)：弹出对象数 \(k'=min(s,k)\)
  • 势差：\(\Theta(D_i)-\Theta(D_{i-1})=(s-k')-s=-k'\)
  • 平摊成本：\(\hat{C}_i=C_i+\Theta(D_i)-\Theta(D_{i-1})=k'-k'=0\)

总的平摊成本：\(T(n)=O(n)\)

二进制计算器

势函数 \(\Theta\)：计数器中 1 的数目

• 初始：势能为 0，\(Φ(D_0)=0\)
• 任一时刻，计数器中 1 的数目非负，\(\Theta(D_i)\geq{0}\)

实际成本：设 \(OP_i\) 中复位数目为 \(t_i\)，置位至多有 1 个，即 \(C_i\leq{t_i+1}\)

势差：设 \(OP_i\) 操作之后，计算器中 1 的数量为 \(b_i\)，即 \(\Theta(D_i)=b_i\)

• 当计算器 \(k\) 位为 1 时，\(b_i=0\)，\(OP_i\) 将 \(k\) 位置为 0，但没有置位为 1，故 \(b_{i-1}=t_i=k\rightarrow{b_i=b_{i-1}-t_i=0}\)
• 当 \(b_i>0\) 时，\(OP_i\) 将 \(t_i\) 位置为 0，一位置为 1，故 \(b_i=b_{i-1}-t_i+1\)
• 综上：\(b_i\leq{b_{i-1}-t_i+1}\)

\[\begin{align} \Delta(D_i)&=\Theta(D_i)-\Theta(D_{i-1})\\ &=b_i-b_{i-1}\\ &\leq{(b_{i-1}-t_i+1)}-b_{i-1}\\ &=1-t_i \end{align} \]

因此，\(\hat{C}_i=C_i+\Delta(D_i)\leq{(t_i+1)+(1-t_i)}=2\)

则 \(n\) 个操作之后的平摊代价为 \(\sum_{i=1}^n\hat{C}_i\leq{\sum_{i=1}^n2=2n=O(n)}\)

动态表

一个存储管理系统，须能根据实际需要来动态地分配与释放存储块。有如下几个操作：

表扩张：表满时插入 \(x\) 引起扩张

1. 申请更大连续表空间的表
2. 原表复制到新表
3. 释放原表
4. 插入 \(x\)

表收缩：表中对象数小于某数目时，删去 \(x\) 引起收缩

1. 申请更小的表
2. 原表复制到新表
3. 释放原表
4. 删去 \(x\)

插入的最大代价

有两种插入情况：

• 只需简单将数据插入到已有的表中
• 需要创建新表，将旧表数据拷贝到新表中，删除旧表（假设创建新表和释放旧表的时间是常数）

\(c_i\) 表示第 \(i\) 个插入操作代价：

\[c_i= \begin{cases} i, & i-1=2^k \\ 1, & otherwise \end{cases} \]

Operation	Table Size	Cost
\(Insert(1)\)	1	1
\(Insert(2)\)	2	1+1
\(Insert(3)\)	4	1+2
\(Insert(4)\)	4	1
\(Insert(5)\)	8	1+4
\(Insert(6)\)	8	1
\(Insert(7)\)	8	1
\(Insert(8)\)	8	1
\(Insert(9)\)	16	1+8

\(N\) 个操作的总代价：

\[\begin{align} T(n)&=\sum_{i=1}^{n}c_i\\ &\leq{n+\sum_{j=0}^{\lfloor lgn \rfloor}2^j}\\ &=n+\frac{2^{\lfloor lgn \rfloor+1}-1}{2-1}\\ &\leq{n+(2n-1)}\\ &<3n \end{align} \]

因此每个操作的平均平摊代价为 \(T(n)/n=O(1)\)

核算法

动态表的插入操作的平摊成本为 3

当一个元素 \(x\) 新插入表中时，收费 3 元

• 1 元支付本身的插入
• 1 元存放到 \(x\) 上作为存款，支付下次扩张时该元素的复制成本
• 1 元作为存款放在上次扩张到本表中（已移动过一次）的某个元素上，作为下次扩张时的复制成本

上面第三块举例来说：设当前表大小为 \(m\)，则 \(m/2\) 个元素是本表扩张前由原表复制过来的，它们没有存款，故当往表中插入后一半元素时，应为前一半元素各存 1 元，当 \(m\) 个表目填满时，各元素均有 1 元支付新扩张的复制费用。

标签：lfloor,摊还,leq,导论,平摊,算法,Theta,操作,代价
From： https://www.cnblogs.com/fireonfire/p/17110409.html