我正在自学TAOCP，并试图理解第2.2.2章线性列表:顺序分配中的以下问题的解决方案。
- [30]设
σ为任意插入和删除序列，如(12)，设s0 (σ)为初始条件(11)下σ应用图4的简单方法所发生的堆栈溢出数，设s1 (σ)为相对于其他初始条件(13)所发生的堆栈溢出数。证明s0 (σ) ≤ s1 (σ)+L∞ − L0.
对于s0，初始条件为BASE[j] = TOP[j] = L0 for 1 <= j <= n(11)，BASE[n+1]=L∞。换句话说，最初所有的空间(L∞ − L0)都给了最后一个堆栈(n-th堆栈)，所有堆栈都是空的。s1可以是任何其他初始条件，例如，将所有空间均匀分配给n空堆栈。
请注意，当堆栈i溢出时，算法是找到最近的未满容量的后续堆栈，并"将其移动一个等级"。如果所有后续堆栈(相对于i)都是满的，那么找到最近的未满的前一个堆栈(相对于i)，并"向下移动一个缺口"。最后，如果不能为新的堆栈项找到任何空间，则必须放弃。
我们的直觉是:
很明显，如果我们明智地选择初始条件，而不是像(11). ...中建议的那样，最初将所有空间分配给第n个堆栈，那么用这种方法发生的许多第一堆栈溢出都可以消除无论初始分配设置得有多好，它最多只能节省固定数量的溢出，而且效果只在程序运行的早期阶段才会明显。
给出的解决方案是:
- 首先显示
BASE[j]0 ≤ BASE[j]1在任何时候。然后观察s0(σ)中i堆栈的每次溢出(s1(σ)中没有溢出)都发生在i堆栈比以前大的时候，但是它的新大小并不超过s1(σ)中分配给i堆栈的原始大小。
我不认为"比以前更大"。这种说法有一部分是对的。一个堆栈的容量可能会因为另一个堆栈溢出而缩小。假设堆栈i已满，然后从堆栈i删除，然后堆栈i缩小，最后插入到堆栈i。在这种情况下，当堆栈i变大时，堆栈i发生溢出，但不是"比以前更大"。由于这个原因，我不理解解决方案，或者看到我应该看到的，我想。
我正试图找出一种方法来证明s0 (σ)最多会遇到L∞ − L0比s0 (σ)更多的溢出，但我目前很困惑。任何帮助都将是感激的:-)
我想你可能有一个合理的反对意见，但我没有接近我的TAoCP副本，我不确定我是否正确实现了算法(参见下面的Python)。
假设我们有n = 4个堆栈。我们从"坏"初始条件(50)开始，其中堆栈0、1、2的容量都为0，堆栈3的容量为4，以及"好"初始条件(s1)，其中每个堆栈的容量为1。
错误的顺序是:push stack 2, pop stack 2, push stack 1, pop stack 1, push stack 0, push stack 1, push stack 2。每次push都溢出50，但不溢出s1。
import random
def push(L, U, i):
if U[i] < L[i + 1]:
U[i] += 1
return False
for k in range(i + 1, len(U)):
if U[k] < L[k + 1]:
for j in range(k, i, -1):
U[j] += 1
L[j] += 1
U[i] += 1
return True
for k in range(i - 1, -1, -1):
if U[k] < L[k + 1]:
for j in range(k + 1, i):
L[j] -= 1
U[j] -= 1
L[i] -= 1
return True
return False
def pop(L, U, i):
if L[i] < U[i]:
U[i] -= 1
def test():
for t in range(1000000):
n = 4
cap = 1
L0 = [0] * n + [n * cap]
U0 = L0[:n]
L1 = list(range(0, (n + 1) * cap, cap))
U1 = L1[:n]
c0 = 0
c1 = 0
ops = []
for r in range(7):
i = random.randrange(n)
if random.randrange(2):
c0 += push(L0, U0, i)
c1 += push(L1, U1, i)
ops.append("push {}".format(i))
else:
pop(L0, U0, i)
pop(L1, U1, i)
ops.append("pop {}".format(i))
assert L0[-1] == n * cap == L1[-1]
assert all(U0[i] - L0[i] == U1[i] - L1[i] for i in range(n))
assert c0 <= c1 + L1[-1], "n".join(ops + [str(c0), str(c1)])
if __name__ == "__main__":
test()