平摊分析典型例题及解答

本是古典何须时尚 2021-12-16 08:17 418阅读 0赞

**Exercise 1.** (5)

对某个数据结构执行大小为 n 的一个操作序列，若 i 为 2 的整数幂，则第 i 个操作的代价 为 i，否则为 1。请利用会计方法分析每次操作的平摊代价

**Exercise 2.** (15)

Bill 提出了一种叫做翻转堆栈的数据结构，翻转堆栈只支持 Flipping-Push() 函数。在每 次 Flipping-Push() 中，首先压栈，并检查堆栈中的对象数目数是否是 2 的幂（2^i )。如果 是，则堆栈中的所有对象将翻转。例如我们使用 Flipping-Push() 将对象 1,2,3,4 压入堆栈 中，堆栈中的内容（从底向上看）在每次压栈后为:

(1) ⇒ (2, 1) ⇒ (2, 1, 3) ⇒ (4, 3, 1, 2) Bill

请求你分别使用聚集分析、会计方法、势能方法分析 Flipping-Push() 函数的平摊代价 (amortized cost), 堆栈反转的代价等于堆栈现有对象数目

**Exercise 3**. (8)

有两个堆栈 A 和 B，都可以使用以下 5 种操作（A 大小为 n，B 大小为 m）:

PushA(x):x 压入堆栈 A，实际代价 =1 PushB(x):x 压入堆栈 B，实际代价 =1

MultiPopA(k): 从 A 中弹出 min\{k, n\} 个元素，实际代价 =min\{k, n\}

MultiPopB(k): 从 B 中弹出 min\{k, m\} 个元素，实际代价 =min\{k, m\}

Transfer(k): 从 A 中弹出元素并压入 B 中，直到转移 k 个元素或 A 为空，实际代价 = 转 移元素数目 (a)MultiPopA(k),MultiPopB(k),Transfer(k) 三种操作最坏情况下的时间复杂度为多少？

(b) 定义一个势能函数 Φ(n, m), 用它证明以上操作平摊代价为 O(1)

因为有些符号打起来比较麻烦，因此我写这些题的时候多是手写的，有空一定重新打出来。QAQ

**Excecise 1.**

对于该数据结构每次操作的平摊代价为3。事实上这题与动态表的扩张完全类似。当i为2的整数幂时，第i个操作的代价为i，这时的操作可看作一次“扩张”。

每次操作的平摊代价为3的具体分析：

1.当它执行一个代价为1的操作；

2.当i为2的整数幂时，“扩张”需要的代价；

3.“扩张”时对一个已经执行过的操作，储存1作为操作的信用。

**Exercise 2**

**见以下图片：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgyMTg3NA_size_16_color_FFFFFF_t_70][]

**Exercise 3.**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgyMTg3NA_size_16_color_FFFFFF_t_70 1][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgyMTg3NA_size_16_color_FFFFFF_t_70]: /images/20211214/3df6e4e646324a80849feee6267b224b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgyMTg3NA_size_16_color_FFFFFF_t_70 1]: /images/20211214/b4da953d0e894286a1f4ea0f3bf7fa89.png