＜Introduction to algorithms＞笔记

Part4 高级设计和分析技术

part1-3中学习的普遍应用的算法思想和技术如下:

分治法 divide and conquer
随机化 randomize
递归求解 recursion

在面对一个计算问题时, 一般的直接解法是暴力破解,即穷举法.从一定意义上讲,所有的最优化问题都可以通过穷举法来解决,但是这在时间上是不可接受的.要更高效的求解问题, 需要学习对高效算法的设计分析技术
所有的高效算法都是为了加快速度:

动态规划:保存子问题的解,以备重复使用
贪心算法:用局部最优解来求全局最优解
平摊分析是用来分析算法的工具,它本身并不是一种算法.

动态规划 dynamic programming
- 动态规划通常应用于最优化问题,即要做出一组选择以达到一个最优解时.在做选择的同时,经常出现同样形式的子问题.关键技术是存储这些子问题每一个的解,以备它重复出现.
贪心算法 greedy algorithm
- 贪心算法通常也是应用于最优化问题,该算法的思想是以局部最优的方式来做每一个选择.采用贪心算法可以比动态规划更快地得出一个最优解,但是关键是不容易判断贪心算法所得到的是否真的是最优解.
平摊分析 amortized analysis
- 平摊分析是一种用来分析执行一系列类似操作的算法的工具.在一个操作序列中,不可能每一个都以其已知的最坏情况运行,某些操作的代价高些,而其它的低一些.平摊分析不分别计算每一次操作的代价确定一系列代价的界,而是对整个操作序列的真实代价限界.

Chapter15 如何利用已经计算出的子问题?

1.动态规划与分治法之间的区别:

分治法是指将问题分成一些独立的子问题,递归的求解各子问题,合并子问题得到原问题的解
动态规划适用于这些子问题不是独立的情况,也就是各子问题包含公共子问题.
对公共子问题,分治法会重复的求解,而动态规划则是只求解一次,保存结果到一张表中,从而避免了重复计算.

以斐波那契数列的计算fib(5)为例

分治法计算如下:

fib(n):
  return fib(n-1) + fib(n-2)
fib(5) = fib(4) + fib(3)
       = (fib(3) + fib(2)) + (fib(2) + fib(1))
       = ((fib(2) + fib(1)) + fib(2)) + (fib(2) + fib(1))

可以看到, fib(2)和fib(1)重复计算多次, 导致时间复杂度为$O(2^n)$

动态规划计算如下

array Fib[];
Fib[1] = 1, Fib[2] = 1;
fib(n):
  if Fib(n) != 0
    return Fib(n)
    else return fib(n-1) + fib(n-2)

每次计算的结果记录在Fib(n)中, 如果计算过程中需要直接取出记录即可, 减少了很多重复计算, 算法复杂度降为$O(n)$

2.最优化问题:
具有多个可行的解, 每个解有一个值,具有最优(Max or Min)值的解是一个最优解.
动态规划多用于最优化问题, 其设计可以分为 4 个步骤:

描述最优解的子结构

递归定义最优解的值

按自底向上的方法计算最优解的值

由计算出的结果反向构造出一个最优解
动态规划最重要的是要找出最优解的子结构

以解决矩阵链式乘法为例来梳理动态规划的步骤:

1.问题背景:
给定n个矩阵构成的序列链 $(A_1, A_2, \ldots, A_n)$, 计算乘积:
$$A_1 A_2 \ldots A_n \qquad (15.1)$$
要计算式(15.1), 考虑计算两个矩阵相乘的子程序matrix-multiply(A, B)
1
2
3
4
5
6
7
8
matrix-multiply(A, B)
if columns[A] != rows[B]
  then error "imcompatible dimensions"
  else for i <- 1 to rows[A]
    do for j <- 1 to columns[B]
      do C[i, j] <- 0
        for k <- 1 to columns[A]
          do C[i, j] <- C[i, j] + A[i, k] * B[k, j]

矩阵的乘积是按括号给出的计算顺序来计算的, 以矩阵链 $(A_1, A_2, A_3, A_4)$ 为例, 就有5种计算顺序:
\begin{align}
(A_1(A_2(A_3A_4))) \\
(A_1((A_2A_3)A_4)) \\
…
\end{align}
以标量乘法次数来衡量复杂度, 从matrix-multiply(A, B)得到,
A阶数pq, B阶数qr -> 复杂度$O(pqr)$
不同的括号顺序导致的矩阵乘积代价不同, 如何求解最小化的代价(即最少的标量乘法次数)的方案?

2.问题求解
如果穷举可能的全部括号方案,可以得到一个结果, 但显然代价太大.设P(n)为矩阵链的加括号方案数, 有:
$$
P(N) =
\begin{cases}
1, \text {if n = 1} \\
\sum_{k=1}^{n=1}P(k)P(n-k),\text {if n >= 2}
\end{cases}
$$
其复杂度为 $O(2^n)$,指数复杂度, 显然穷举搜索不是好的策略.
a. 最优子结构
\begin{align}
记A_{i \dots j} 为乘积A_iA_{i+1} \dots A_j \\
对 i\leq k < j, 复杂度为 \\
O(A_{i \dots j}) = O(A_{i \dots k}) + O(A_{k+1 \dots j}) + O(A_{i \dots k} * A_{k+1 \dots j}) \\
\because 如果A_{k+1} \dots A_j的最优加括号方案不是A_iA_{i+1} \dots A_j的最优加括号方案的子链,\\
则用A_{k+1} \dots A_j的最优加括号方案得到的O(A_{i \dots j})更小 \\
\therefore 最优子结构: \\
A_{k+1} \dots A_j的最优加括号方案是A_iA_{i+1} \dots A_j的最优加括号方案的子链
\end{align}

b. 递归求解
根据子问题的最优解递归定量定义最优解的代价
\begin{align}
记m[i,j]为计算A_{i \dots j}的标量乘法次数的最小值 \\
m[i, j] =
\begin{cases}
0, \text {if i = j} \\
min_{i \leq k < j}\{m[i,k] + m[k+1,j] + p_{i-1} p_k p_j \},else
\end{cases}
记s[i, j] = k 为最优加括号方案的子链分裂点k
\end{align}

c. 计算最优代价
这个递归式在递归树的不同分支上会多次遇到同一子问题(即重复的矩阵子链,类似斐波那契数列的递归解法), 即有明显的公共子问题的特点.因此如果直接递归的求解递归式,会陷入对相同子链的重复计算,增加算法复杂度, 所以采用自底向上的表格法计算最优代价如下
\begin{align}
设A_i的阶数p_{i-1}*p_i, i = 1,2,\dots,n \\
则矩阵链[A_1, A_2, \ldots, A_n的阶数序列记为 p=[p_0,p_1,\dots,p_n] \\
表m[1\dots n, 1\dots n]记录m[i, j]的代价 \\
表s[1\dots n, 1\dots n]记录计算m[i,j]取得最优代价的k值 \\
\end{align}
1
2
3
4
5
6
7
8
9
10
11
12
13
matrix-chain-order(p)
  n <- length[p] - 1 # 矩阵链长度n
  for i <- 1 to n
    do m[i,i] <- 0 #长度为1的链代价为0
  for l <- 2 to n #计算长度为l的链的代价
    do for i <- 1 to n - l + 1
      do j <- i + l - 1
        m[i,j] <- INT
        for k <- i to j - 1
          do q <- m[i,k] + m[k+1,j] + p(i-1)p(k)p(j)
            if q < m[i,j]
              then m[i,j] <- q;s[i,j] <- k
  return m and s

matrix-chain-order算法从长度为1的链开始循环计算, 每次计算m[i,j]时仅依赖于已经计算出的m[i,k]和m[k+1,j], 这正是核存储公共子问题的解,以减少重复计算的核心方法.

d. 构造最优解
matirx-chain-order计算了最少的标量乘法次数,但并没有给出如何加括号确定矩阵相乘的方案.此时s[i,j]发挥作用,知按最优方案计算$A_{1 \dots n}$, 最后一步递归的子链相乘次序是$A_{1 \dots s[1,n]}A_{s[1,n]+1 \dots n}$, 之前的则递归的进行.递归输出最优方案的算法如下
1
2
3
4
5
6
7
print-optimal-parens(s, i, j)
  if i = j
    then print "A"(i)
    else print "("
      print-optimal-parens(s, i, s[i,j])
      print-optimal-parens(s, s[i,j]+1, j)
      print ")"

3.动态规划基础
从矩阵链乘法问题我们可以归纳,采用动态规划方法求解最优化问题的两个要素:

最优子结构 Optimal substructure

如果问题的一个最优解中包含了子问题的最优解,则该问题具有最优子结构;而当一个问题具有最优子结构时,提示我们动态规划可能会适用.在矩阵链乘法问题中,$A_iA_{i+1} \dots A_j$的最优加括号方案就包括了$A_iA_{i+1} \dots A_k$和$A_kA_{k+1} \dots A_j$这两个自问的最优解.
那么如何寻找最优子结构?有下面的模式可以遵循:

问题的解一般是一种决策或选择.矩阵链乘法问题即选择在哪里分裂矩阵链

对给定的问题,假设已知的是一个导致最优解的选择

已知这个选择后,确定子问题,和如何描述子问题

使用剪贴技术(cut and paste)用来证明在问题的一个最优解中,使用的子

问题的解本身也必须是最优的.即用反证法,”剪除”非最优问题的解再”贴上”最优解,证明可以得到原问题的更好的解,与假设已经得到的最优解相矛盾.
最优子结构在问题域中以两种方式变化(在找出这两个问题的解之后,构造出原问题的最优子结构往往就不是难事了):

有多少个子问题被用在原问题的一个最优解中

在决定一个最优解中使用哪些子问题有多少个选择

非正式地:一个动态规划算法的运行时间依赖于两个因素的乘积:子问题的总个数和每个子问题中有多少种选择.问题解的代价通常是子问题的代价加上选择本身带来的开销.例如,在矩阵链乘法问题中,选择矩阵$A_k$分裂为子链, 再加上选择的代价$p_{i-1}p_kp_j$.
动态规划能够消除重复计算子问题是因为它与普通递归相反,它是通过自下而上的方式来进行求解的.动态规划正是一个递归的反向展开的过程:
在满足1.最优子结构 2.重叠子问题这2个条件下,通过把递归从下至上的进行展开以避免重复计算子问题从而加速了最终问题的求解的过程.
注: 在不能应用最优子结构的时间,就一定不能假设它能够应用.

重叠子问题 Overlapping subproblems

最优化问题要求解原问题的递归算法可反复解同样的子问题,而不是产生新的子问题.
一般的,不同的子问题的数目是输入规模的一个多项式.这样,动态规划算法才能充分利用重叠的子问题,减少计算量.即通过每个子问题只解一次,把解保存在一个需要时就可以查看的表中,而每次查表只需要常数时间.
如在矩阵链乘法中,matrix-chain-order解更大问题时,反复取出较小的子问题.比如m[3,4]计算被使用四次:在计算m[2,4],m[1,4],m[3,5]和m[3,6]被使用.相比较的,如果采用低效率的递归程序产生的递归树,反复计算m[i,j],导致复杂度骤升到$O(2^n)$
1
2
3
4
5
6
7
8
9
recursive-matirc-chain(p, i, j)
  if i = j
    then return 0
  m[i,j] <- INT
  for k <- i to j - 1
    do q <- recursive-matirc-chain(p, i, k) + recursive-matirc-chain(p, k+1, j) + p(i-1)p(k)p(i)
    if q < m[i, j]
      then m[i,j] <- q
  return m[i,j]

4.备忘录方法 memorandum method

备忘录方法:这种方法是动态规划的一个变形,它本质上与动态规划相同,但是比动态规划更好理解.步骤如下:

使用普通的递归结构,自上而下的解决问题.

当在递归算法的执行中每一次遇到一个子问题时,就计算它的解并填入一个表中.以后每次遇到该子问题时,只要查看并返回表中先前填入的值即可.

从这段描述可以看出:动态规划与递归时做备忘录的本质是完全相同的,所以说备忘录方法与普通的动态递归本质完全相同,没有孰优孰劣之分,哪个方便用哪个.

从备忘录方法求解矩阵链问题如下:

memoized-matirx-chain(p)
  n <- length[p] - 1
  for i <- i to n
    do for j <- i to n
      do m[i,j] <- INT
  return lookup-chain(p, 1, n)

#查表
lookup-chain(p, i, j)
  if m[i,j] < INT
    then return m[i,j]
  if i = j
    then m[i,j] <- 0
    else for k <- i to j - 1
      do q <- lookup-chain(p,i,k) + lookup-chain(p,k+1,j)+p(i-1)p(k)p(j)
      if q < m[i,j]
        then m[i,j] <- q
  return m[i,j]

备忘录方法与动态递归方法的比较:

如果所有的子问题都至少要被计算一次,则一个自底向上的动态规划算法通常比一个自顶向下的做备忘录算法好出一个常数因子.因为动态规划没有使用递归的代价,只用到了循环,所以常数因子肯定比递归要好一些.

此外,在有些问题中,还可以用动态规划算法中的表存取模式来进一步的减少时间和空间上的需求;或者,如果子问题中
的某些子问题根本没有必须求解,做备忘录的方法有着只解那些肯定要求解的子问题的优点.(而且这点是自动获得的,那些不必要计算的子问题在备忘录方法中会被自动的抛弃)

备忘录方法总结:由“是否所有的子问题都至少需要被计算一次”来决定使用动态规划还是备忘录.这两种方法没孰优孰劣之分,因为它们的本质思想是完全一样的;消除重复子问题.

Chapter16 局部最优能得到全局最优吗?

最优化问题如果采用动态规划可能设计分析过于复杂,这时可以选择贪心算法.
贪心算法使所作的选择看起来都是当前最佳的,期望通所做的局部最优选择来产生一个全局最优解.对算法中的每一个决策点,做一个当时看起来是最佳的选择,这种启发式策略并不是总能产生最优解的.

1.活动选择问题

有一个需要使用每个资源的n个活动组成的集合$S= {a_1,a_2,\dots,a_n}$,资源每次只能由一个活动使用.每个活动$a_i$都有一个开始时间$s_i$和结束时间$f_i$,且 $0 < s_i < f_i < \infty$.一旦被选择后,活动$a_i$就占据半开时间区间 $[s_i,f_i)$ .如果 $[s_i,f_i] [s_j,f_j)$ 互不重叠,则称 $a_i$和 $a_j$两个活动是兼容的.该问题就是要找出一个由互相兼容的活动组成的最大子集.
动态规划与贪心求解该问题
a. 最优子结构
子问题空间:
$$S_{ij} = \{a_k \in S: f_i \leq s_k < f_k \leq s_j \}$$
定义子问题解空间 $S_{ij}$ 是S的子集,其中的每个获得都是互相兼容的.即每个活动都是在 $a_i$ 结束之后开始,且在 $a_i$ 开始之前结束.为了方便计算,添加两个虚构活动 $a_0$ 和 $a_{n+1}$ ,其中$f_0=0,s_{n+1}= \infty$.
按活动结束时间单调递增排序
$$f_0 \leq f_1 \leq \dots \leq f_n \leq f_{n+1}$$
可以得到：当$i \geq j$时,$S_{i,j}$ 为空集.如果活动按照结束时间单调递增排序,子问题空间被用来从 $S_{i,j}$ 中选择最大兼容活动子集,其中 $0≤i＜j≤n+1$,所以其他的 $S_{i,j}$ 都是空集.
最优子结构为:假设 $S_{ij}$ 的最优解 $A_{ij}$ 包含活动 $a_k$,则对 $S_{ik}$ 的解 $A_{ik}$ 和 $S_{kj}$ 的解 $A_{kj}$ 必定是最优的.通过一个活动 $a_k$ 将问题分成两个子问题,下面的公式可以计算出$S_{ij}$的解 $A_{ij}$:
$$A_{ij} = A_{ik} \bigcup \{a_k\} \bigcup A_{kj}$$

b.一个递归解
设c[i, j]为 $S_{ij}$ 中最大兼容子集中的活动数目,当 $S_{ij}$ 为空集时,c[i, j]=0；当$S_{ij}$非空时,若 $a_k$ 在 $S_{ij}$ 的最大兼容子集中被使用,则则问题 $S_{ik}$ 和 $S_{kj}$ 的最大兼容子集也被使用,故可得到$c[i, j] = c[i, k] + c[k, j] + 1$
故有
$$
c[i, j] =
\begin{cases}
0, if \, S_{ij} = \emptyset \\
max_{i<k<j}\{c[i,k]+c[j,k]+1\},else
\end{cases}$$

c.最优解计算过程
采用动态规划可以直接解决,但针对活动选择问题可以有效简化，认真分析可以得出以下定理：对于任意非空子问题 $S_{ij}$ ，设 $a_m$ 是 $S_{ij}$ 中具有最早结束时间的活动,
$$f_m = min \{ f_k: a_k \in S_{ij} \}$$
有:

$a_m$ 在 $S_{ij}$ 中的某最大兼容活动子集中被使用.

$S_{im}$ 为空，所以选择 $a_m$ 将使子问题 $S_{mj}$ 为唯一可能非空的子问题.

有这个定理，就简化了问题，使得最优解中只使用一个子问题，在解决子问题 $S_{ij}$ 时，在 $S_{ij}$ 中选择最早结束时间的那个活动.这样的贪心决策,使得剩下的,未调度的时间最大化.
贪心算法自顶向下地解决每个问题，解决子问题 $S_{ij}$ ，先找到 $S_{ij}$ 中最早结束的活动 $a_m$ ，然后将 $a_m$ 添加到最优解活动集合中，再来解决子问题 $S_{mj}$ .
递归解法如下:
1
2
3
4
5
6
7
recursive-activity-selector(s, f, i, j)
  m <- i + 1
  while m < j and s(m) < f(i)
    do m <- m + 1
  if m < j
    then return {a(m)} and recursive-activity-selector(s, f, m, j)
    else return none

根据尾递归的形式转化为迭代算法:

greedy-activity-selector(s, f)
  n <- length[s]
  A <- {a(i)}
  i <- 1
  for m <- 2 to n
    do if s(m) > f(i)
      then A <- A and {a(m)}
        i <- m
  return A

2.动态规划与贪心的关系

从活动选择问题可以看到, 我们先用动态规划的思想解决, 继而发现可以增强条件,使用在动态规划基础上的贪心算法, 更高效的解决问题.贪心算法基础上有一个动态规划算法来证明其正确性,所以说安全的(能够取得最优解的).所以动态规划其实是“安全的贪心算法”的基础.无论如何,在每一个贪心算法的下面,几乎总是会有一个更加复杂的动态规划解.贪心算法实现简单速度快,但是证明贪心的正确性往往是很困难的,要在本已经较为复杂的动态规划证明上确定贪心的正确性.

3.贪心算法的一般步骤:

将优化问题转化成这样的一个问题,即先做出选择(对应于动态规划的先解决子问题再选择),再解决剩下的一个子问题.

证明原问题总是有一个最优解是做贪心选择得到的,从而说明贪心选择的安全.

说明在做出贪心选择后,剩余的子问题具有这样的一个性质.即如果将子问题的最优解和我们所做的贪心选择联合起来,就可以得出原问题的一个最优解.

正确使用贪心算法的2个关键要素:贪心选择性质和最优子结构.

贪心选择性质:一个全局最优解可以通过局部最优(贪心)选择来达到;即当考虑做何选择时,我们只考虑对当前问题最佳的选择而不考虑子问题的结果.

最优子结构:一个问题的最优解包含了其子问题的最优解.

对应的,要使用贪心算法就必须先证明以下两个性质:

每一步所做的贪心选择最终能产生一个全局最优解.在证明中先考察一个全局最优解,然后证明对该解加以修改,使其采用贪心选择,这个选择将原问题变为一个相似的、但更小的问题.

子问题的最优解与所做的贪心选择合并后,的确可以得到原问题的一个最优解.

4.应用

一般地,就算证明不出来贪心算法能给出最优解,但是它一般都至少能给出次优解.所以贪心算法在实际的应用中是非常的普及的.

Chapter17 较复杂的操作怎样平摊到所有操作上?

1.平摊分析 amortized analysis
在平摊分析中,执行一系列数据结构操作所需要的时间是通过对执行所有操作所花费的时间求平均而得到的.平摊分析表明不能总以最坏情况来衡量算法,因为最坏的情况并不经常会发生,甚至在绝大多数应用中最坏情况出现的次数是极少的.

平摊分析与平均情况分析的不同之处在于它不牵涉到概率;平摊分析保证在最坏情况下,每个操作具有平均性能.通过平摊分析,可以获得对某种特定数据结构的认识,这种认识有助于优化设计.
一个例子是 C++ STL 中 vector.push_back 操作,一般情况下push_back追加到vector只需要复杂度$O(1)$, 但在vector达到容量限度时,vector先要动态扩展,然后push_back,复杂度升到$O(n)$,这种最坏情况出现次数相对于一般情况出现很少,对所有操作求平均后,每个push_back具有 $O(1)$的性能.

2.平摊分析的三种方法:

聚集分析:指分析一系列操作的总时间的上节$T(n)$, 平均代价即为$T(n)/n$

记账法:对每次操作的对象进行预先记账,补偿实际代价高于帐的操作

势能方法:与记账法类似,但将每次预留的势能视为是整个数据结构共享的,整体维护

3.聚集分析: aggregate analysis

由N个操作所构成的序列的总时间在最坏的情况下为$T(n)$,则每个操作的平均代价(平摊代价)为$T(n)/n$.以前的时间复杂度分析都是以单次操作为对象的分析它的最坏时间复杂度,而聚集分析所分析的是N次操作的总时间的最坏情况.
聚集分析:由序列的总最坏时间 -> 单次的平摊时间
以stack的操作为例(增加一个操作multipop, 连续出栈)
1
2
3
4
5
6
push(S, x): O(1)
pop(S): O(1)
multipop(S, k): O(n)
  while not stack-empty(S) and k != 0
    do pop(s)
      k <- k - 1

则n个包含push和pop的序列总代价为 $O(n)$ , 但加上复杂度为 $O(n)$ 的multipop操作后,应该如何计算?
任意stack操作的最坏时间复杂度为$O(n)$, 故N个操作的代价是 $O(2^n)$.但这个界明显过大, 因为不可能出现连续n次multipop的情况.
但从pop和push对应的角度考虑,
因为一个对象入栈后最多出栈一次, 将multipop视为pop的连续操作
所以pop的次数 $\leq$ push的次数
n个序列的总时间代价为$O(n)$,平均代价为$O(n)/n=O(1)$

4.记账法: bookkeeping method

对序列操作中的每一个操作收取一定的费用,当所收取的费用比它实际应支付的费用多时就把多余的部分当作存款(credit)存起来,一个操作的平摊代价可以看作两部分:实际代价和存款(或被储蓄或被用完).其要素为:

存款可以用来在以后补偿那些其平摊代价低于其实际代价的操作.

如果希望通过对平摊代价的分析来说明每次操作的最坏情况平均代价较小,则操作序列的总平摊代价就必须是该序列的总的实际代价的一个上界.因为平摊代价是最坏时的平均代价,即存款不能为负.

存款不能为负,因为记账法是不允许欠账的,否则就不能满足平摊代价是操作总时间的最坏情况的平均这个定义.

对于前面的stack操作,各操作的实际代价和平摊代价如下:

操作	实际代价	平摊代价
push	1	2
pop	1	0
multipop	min(k, s)	0

平摊代价当每次入栈时记账支付2元,其中1元支付该push操作的实际代价,还有1元用于支付该元素被pop出来时的代价.则可以保证在任何时间内都不会有欠账,故pop操作可以不收取任何费用.

5.势能方法: potential method

将已预付的工作作为一种“势能”保存,它在需要时可以释放出来,以支付后面的操作.势能是与整个数据结构而不是其中的个别对象发生联系的.相对比, 记账法中的账与个别对象发生联系,比如栈操作时支付的2元就记在入栈的那个元素上)
\begin{align}
初始数据结构D_0, 记c_i为第i个操作的实际代价 \\
D_i为数据结构D_{i-1}作用第i操作的的结果 \\
势函数\Phi: D_i \mapsto \Phi(D_i) \\
平摊代价 \hat{c_i} = c_i + \Phi(D_i) - \Phi(D_{i-1}) \\
总平摊代价 \sum_{i=1}^n\hat{c_i} = \sum_{i=1}^n(c_i + \Phi(D_i) - \Phi(D_{i-1})) = \sum_{i=1}^n c_i + \Phi(D_n) - \Phi(D_0)
\end{align}

仍然以stack操作为例,
\begin{align}
定义势函数\Phi 为stack中对象个数 \\
初始空stack D_0, \Phi(D_0) = 0 \\
push操作: \\
\hat{c_i} = c_i + \Phi(D_i) - \Phi(D_{i-1}) = 1 + (s+1) - s = 2 \\
multipop操作: \\
\hat{c_i} = c_i + \Phi(D_i) - \Phi(D_{i-1}) = k + (s -k) - s = 0 \\
\therefore 每一操作平摊代价为O(1) \\
\therefore n个操作最坏代价为O(n)
\end{align}