3 tape, 2-way merge
证明: 如果初始只有一个磁带中有 \(F_N\) 个数据, \(F_N\) 是斐波那契数, 那么最好的分割方案是将 \(F_N\) 分割成 \(F_{N-1}\) 和 \(F_{N-2}\)
严格证明想不太出来
只有一个感性理解
对于 \(F_{k+1}\), 分割成的两个数如果不是斐波那契数, 那么假设分成了 \(F_k+t\) 和 \(F_{k-1}-t\)
那么这个差异 \(t\) 会以斐波那契数列的形式增长, 直到它增大到使得某一侧过大
原本的斐波那契数列会减小到 \(1,1\) 才出现等于号, 之前一直是大于小于不断变化
而现在偏大的一侧减去另一侧后符号不变
如果 \(t=1\), 那么这个临界点会在 \(k=N/2\) 左右出现
所以数列的衰减速率从指数级 (以黄金分割比 \(\phi\) 衰减), 变成了分数衰减 (一直减去小的那一侧衰减)
如果大/小的比值很大, 那么数列的衰减会变慢许多
这导致了这样分割不如分成斐波那契数列
具体地说, 假设 \(t=1\), 那么:
1. \(F_1\) 前是正号
从 \(F_N+F_1 > F_{N-1}-F_2\) 开始
\(F_N+F_1 > F_{N-1}-F_2\)
\(F_{N-2}+F_3 < F_{N-1}-F_2\)
\(F_{N-2}+F_3 > F_{N-3}-F_4\)
\(F_{N-4}+F_5 < F_{N-3}-F_4\)
\(\vdots\)
直到某个地方开始符号不变
正常的符号:
\(F_{N-k}+F_{k+1}<F_{N-k+1}-F_k\) 或 \(F_{N-k}+F_{k+1}>F_{N-k-1}-F_{k+2}\)
现在变成:
\(F_{N-k}+F_{k+1}>F_{N-k+1}-F_k\) 或 \(F_{N-k}+F_{k+1}<F_{N-k-1}-F_{k+2}\)
那么从这里开始大减小, 直到符号改变
对于第一个 \(F_{N-k}+F_{k+1}>F_{N-k+1}-F_k\)
移项得 \(F_{k+2}>F_{N-k-1}\)
\(k>\frac{N-3}{2}\)
假设 \(k=N/2-1\)
代入原式
\(F_{N/2+1}+F_{N/2}>F_{N/2+2}-F_{N/2-1}\)
可以化简成
\(F_{N/2+2}>2F_{N/2}\)
由于 \(\displaystyle \lim_{N\to\infty}\frac{F_{N/2+1}+F_{N/2}}{F_{N/2+2}-F_{N/2-1}}=\frac{F_{N/2+2}}{2F_{N/2}}=\frac{\phi^2}{2}=1.3\)
所以大概会以分数速率多衰减 \(\displaystyle \lceil\frac{\phi^2}{2}\rceil=2\) 次
如果 \(\displaystyle\frac{F_{N/2+2}}{2F_{N/2}}\) 不是整除, 令 \(F_{N/2+2}-c\cdot 2F_{N/2} = r\) 为余数
之后变成 \(r<2F_{N/2}\)
\(r\) 可以凑成 \(F_{N/2+1}\)
因为 \(2F_{N/2}<F_{N/2}+F_{N/2+1}=F_{N/2+2}\), 所以 \(2F_{N/2}\) 可以凑成 \(F_{N/2+2}\)
凑成 \(F_{N/2+1}<F_{N/2+2}\) 继续指数衰减
假设两种布局从 \(F_{N/2+2}\) 开始以最优速率衰减
那么 \(F_N+F_1 > F_{N-1}-F_2\) 的布局与 \(F_N>F_{N-1}\) 的布局只在 \(N/2+2\) 处有差异
并且前者比后者多出大概 \(\displaystyle \lceil\frac{\phi^2}{2}\rceil\) 次
所以后者是更优的
对于第二种情况 \(F_{N-k}+F_{k+1}<F_{N-k-1}-F_{k+2}\)
\(F_{k+3}<-F_{N-k-2}\)
这个符号在 \(F_1\) 前是正号时无法成立, 所以忽略
综上, 分割成两个斐波那契数更优
例如, 对于 \(55>34\) 变成 \(56>33\)
\(56>33\)
\(23<33\)
\(23>10\)
\(13>10\)
\(3<10\)
凑成 \(8<13\)
\(\vdots\)
\(1=1\)
结束
从 \(13>10\) 到 \(3<10\) 多了 \(2\) 次
2. \(F_1\) 前是负号
从 \(F_N-F_1 > F_{N-1}+F_2\) 开始
\(F_N-F_1 > F_{N-1}+F_2\)
\(F_{N-2}-F_3 < F_{N-1}+F_2\)
\(F_{N-2}-F_3 > F_{N-3}+F_4\)
\(F_{N-4}-F_5 < F_{N-3}+F_4\)
\(\vdots\)
直到某个地方开始符号不变
正常的符号:
\(F_{N-k}-F_{k+1}<F_{N-k+1}+F_k\) 或 \(F_{N-k}-F_{k+1}>F_{N-k-1}+F_{k+2}\)
现在变成:
\(F_{N-k}-F_{k+1}>F_{N-k+1}+F_k\) 或 \(F_{N-k}-F_{k+1}<F_{N-k-1}+F_{k+2}\)
那么从这里开始大减小, 直到符号改变
对于第一个 \(F_{N-k}-F_{k+1}>F_{N-k+1}+F_k\)
\(-F_{N-k-1}>F_{k+2}\)
不可能成立
对于第二种情况 \(F_{N-k}-F_{k+1}<F_{N-k-1}+F_{k+2}\)
\(F_{N-k-2}<F_{k+3}\)
\(N-k-2<k+3\)
\(k>\frac{N-5}2\)
假设 \(k=N/2-2\)
\(F_{N/2+2}-F_{N/2-1}<F_{N/2+1}+F_{N/2}\)
由于 \(\displaystyle \lim_{N\to\infty}\frac{F_{N/2+1}+F_{N/2}}{F_{N/2+2}-F_{N/2-1}}=\frac{F_{N/2+2}}{2F_{N/2}}=\frac{\phi^2}{2}\)
所以同样会以分数速率多衰减 \(\displaystyle\lceil\frac{\phi^2}{2}\rceil\) 次
这样分割成 \(F_{N}>F_{N-1}\) 也是更优的
例如, 对于 \(55>34\) 变成 \(54>35\)
\(54>35\)
\(19<35\)
\(19>16\)
\(3<16\)
\(3<13\)
\(\vdots\)
\(3>1\)
凑成 \(3>2\)
\(1<2\)
\(1=1\)
结束
从 \(3<13\) 到 \(3>1\) 多了 \(5\) 次
实际多了 \(3\) 次, 因为 \(3<13\) 时 \(3\) 已经比较小, 所以略过了原本中间的 \(13\to8\to5\) 这些步骤
这是 \(N\) 比较小所导致的, \(k\) 与期望的 \(N/2-2\) 差异比较大
当 \(N\) 比较大时, 可能会更接近 \(\displaystyle\lceil \frac{\phi^2}{2}\rceil\) 这个次数
3. \(F_1\) 前有非 \(1\) 系数
分析 \(F_N+cF_1>F_{N-1}-cF_2\)
\(F_N+cF_1>F_{N-1}-cF_2\)
\(F_{N-2}+cF_3>F_{N-1}-cF_2\)
\(\vdots\)
直到某个地方开始符号不变
正常的符号:
\(F_{N-k}+cF_{k+1}<F_{N-k+1}-cF_k\) 或 \(F_{N-k}+cF_{k+1}>F_{N-k-1}-cF_{k+2}\)
现在变成:
\(F_{N-k}+cF_{k+1}>F_{N-k+1}-cF_k\) 或 \(F_{N-k}+cF_{k+1}<F_{N-k-1}-cF_{k+2}\)
那么从这里开始大减小, 直到符号改变
对于第一个 \(F_{N-k}+cF_{k+1}>F_{N-k+1}-cF_k\)
\(cF_{k+2}>F_{N-k-1}\)
\(\displaystyle c\frac{\phi^{k+2}}{\phi^{N-k-1}}=c\phi^{2k+3-N}>1\)
\(2k+3-N>\log_{\phi}{\frac1c}\)
\(\displaystyle k>\frac{N-\log_{\phi}{c}-3}{2}\)
假设 \(\displaystyle k=N/2-1-\lceil \log_{\phi}{c}/2\rceil=N/2-1-t\)
\(F_{N/2+1+t}+cF_{N/2-t}>F_{N/2+2+t}-cF_{N/2-1-t}\)
\(\displaystyle \lim_{N\to \infty}\frac{left}{right}=\frac{\phi^{2t+2}+c\phi}{\phi^{2t+3}-1}\)
且由于 \(2t=\log_{\phi}c, \phi^{2t}=c\)
并且 \(\phi+1=\phi^2\)
\(\displaystyle \therefore =\frac{c(\phi+\phi^2)}{c\phi^3-1}=\frac{2c\phi+c}{2c\phi+c-1}\)
所以多出了 \(\displaystyle \lceil \frac{2c\phi+c}{2c\phi+c-1} \rceil\) 步
k+1 tape, k-way merge
太难写了, 不写了