§E16.19償却解析

証明. 長さ$N$の操作列$\sigma=(o_1,\dots,o_N)$をとる。$\hat T$が定数$T$である場合の償却計算量の上界の定義により$\sum_{i=1}^{N}c_i\le\sum_{i=1}^{N}T=TN$である。$\sigma$は任意であったから、最大値についても$C(N)\le TN$である。

§D2.8 定義 2.2の意味で$C(N)=O(N)$であることを確かめる。$c=T+1>0$と$n_0=0$をとると、すべての$N\ge n_0$について$0\le C(N)\le TN\le cN$が成り立つ。▨

証明.(2)$\Rightarrow$(1)を示す。$D_0$から始まる操作列$\sigma=(o_1,\dots,o_N)$をとる。主張 (2)を$k=N$に適用すると$R_N(\sigma)\ge0$、すなわち

である。これは償却計算量の上界の定義そのものである。

(1)$\Rightarrow$(2)を示す。$D_0$から始まる操作列$\sigma=(o_1,\dots,o_N)$と$0\le k\le N$をとる。接頭列$\sigma|_k=(o_1,\dots,o_k)$も$D_0$から始まる有限操作列であり、定義 1.1のとおり、その第$i$操作の実費用は$\sigma$の第$i$操作の実費用$c_i$に等しい。主張 (1)を$\sigma|_k$へ適用すると

であり、これは$R_k(\sigma)\ge0$にほかならない。▨

証明.主張 (1)を示す。償却費用の定義により

である。右辺の第二項は隣り合う項が打ち消し合う望遠鏡和であり、$N$についての帰納法により$\Phi(D_N)-\Phi(D_0)$に等しい。実際、$N=0$のとき両辺は$0$である。$N-1$まで成り立つとすると、第二項は$\bigl(\Phi(D_{N-1})-\Phi(D_0)\bigr)+\bigl(\Phi(D_N)-\Phi(D_{N-1})\bigr)=\Phi(D_N)-\Phi(D_0)$である。

主張 (3)を先に示す。$D_0$から始まる操作列$\sigma=(o_1,\dots,o_N)$について$\Phi(D_N)\ge\Phi(D_0)$が成り立つとする。主張 (1)を移項すると

である。仮定$\hat c_i\le\hat T(o_i)$を加えると$\sum_{i=1}^{N}c_i\le\sum_{i=1}^{N}\hat T(o_i)$を得る。$\sigma$は任意であったから$\hat T$は償却計算量の上界である。

主張 (2)を示す。$D_N$は$D_0$から始まる操作列によって到達可能であるから、仮定により$\Phi(D_N)\ge0=\Phi(D_0)$である。よって主張 (3)の条件が満たされ、同項により主張が従う。▨

証明.$t=t(x)$の定義により$x_0=\dots=x_{t-1}=1$かつ$x_t=0$である。よって

である。右端の式は、第$0$桁から第$t-1$桁までが$0$、第$t$桁が$1$、第$j$桁（$j>t$）が$x_j$である二進表記であり、二進表記の一意性により$(x+1)_j$はこのとおりである。

主張 (1)を示す。$j<t$では$x_j=1$かつ$(x+1)_j=0$、$j=t$では$x_t=0$かつ$(x+1)_t=1$、$j>t$では$x_j=(x+1)_j$である。よって異なる桁は$j=0,1,\dots,t$のちょうど$t+1$個であり、$c(x,\mathrm{inc})=t+1$である。

主張 (2)を示す。$\beta(x)=t+\sum_{j>t}x_j$であり$\beta(x+1)=1+\sum_{j>t}x_j$である。差をとると$\beta(x+1)-\beta(x)=1-t$を得る。

主張 (3)を示す。主張 (1)により、$x$と$x+1$の第$j$桁が異なることは$j\le t$と同値である。一方、上の表示から$x+1=2^{t}\bigl(1+\sum_{j>t}x_j2^{j-t}\bigr)$であり、括弧の中は奇数である。したがって$2^{j}\mid x+1$であることと$j\le t$であることは同値である。二つの同値を合わせて主張を得る。▨

証明.$D_{i-1}=i-1$であるから$c_i=c(i-1,\mathrm{inc})=\lvert\{j\ge0:\ (i-1)_j\ne i_j\}\rvert$である。$j\ge0$と$1\le i\le N$について、$(i-1)_j\ne i_j$が成り立つとき$1$、そうでないとき$0$をとる量を考え、その総和を二通りに数える。

$i$を先に固定して$j$について加えると、和は$\sum_{i=1}^{N}c_i$である。$j$を先に固定して$i$について加えると、補題 4.2 (3)により

である。$2^{j}>N$のときこの値は$0$であるから、$j$についての和は有限個の項だけからなり、和の順序を入れ替えることができる。よって主張の等式を得る。

評価については、$\lfloor N/2^{j}\rfloor\le N/2^{j}$であり、$2^{j}>N$の項が$0$であることから、$2^{J}\le N<2^{J+1}$を満たす非負整数$J$（$N\ge1$のとき）をとって

である。$N=0$のときは両辺とも$0$である。▨

証明.$k$についての帰納法で示す。$k=0$のとき$R_0(\sigma)=0$であり$\beta(D_0)=\beta(0)=0$であるから等式が成り立つ。

$k\ge1$とし、$R_{k-1}(\sigma)=\beta(D_{k-1})$を仮定する。信用残高の定義により

であり、補題 4.2 (1)により$c(D_{k-1},\mathrm{inc})=t(D_{k-1})+1$であるから、この差は$1-t(D_{k-1})$である。一方、$D_k=D_{k-1}+1$と補題 4.2 (2)により

である。二つの差が一致するので、帰納法の仮定と合わせて$R_k(\sigma)=\beta(D_k)$を得る。

$\beta$は桁の個数であるから非負であり、$R_k(\sigma)\ge0$である。定理 2.1 (2)から 1 への含意により$\hat a$は償却計算量の上界であり、長さ$N$の操作列の総費用は$\sum_{i=1}^{N}\hat a(\mathrm{inc})=2N$以下である。▨

証明.$\Phi(D_0)=\beta(0)=0$であり、$\beta$は非負整数であるから$\Phi\ge0$である。償却費用は、補題 4.2 (1)と 2 により

である。よって$\hat c_i\le\hat T(\mathrm{inc})=2$が成り立ち、定理 3.1 (2)の仮定がすべて満たされる。▨

証明.$x=2^{M}-1$と置く。$D_0=0$から$x$回の増加操作を行うと状態は$x$になるので、$x$は到達可能である。$x$の二進表記は第$0$桁から第$M-1$桁までが$1$、第$M$桁以上が$0$であるから$t(x)=M$であり、補題 4.2 (1)により$c(x,\mathrm{inc})=M+1\ge M$である。▨

証明.主張 (1)を示す。$\delta$はいずれの場合も第一成分を$1$だけ増やし、$n_0=0$である。$k$についての帰納法により$n_k=k$である。

主張 (2)を示す。$k$についての帰納法で示す。$k=1$のとき、$n_0=0=m_0$であるから第$1$操作は再確保であり$m_1=\max\{1,0\}=1$である。$1$以上の$2$の冪のうち最小のものは$1$であるから主張が成り立つ。

$1\le k<N$とし、$m_k$が$k$以上の$2$の冪のうち最小のものであると仮定する。主張 (1)により$n_k=k$である。

$k<m_k$の場合、第$k+1$操作は再確保ではなく$m_{k+1}=m_k$である。$m_k$は$2$の冪であり$m_k>k$であるから$m_k\ge k+1$である。$k+1$以上の$2$の冪は$k$以上でもあるから、帰納法の仮定によりそれは$m_k$以上である。よって$m_k$は$k+1$以上の$2$の冪のうち最小のものである。

$k=m_k$の場合、第$k+1$操作は再確保であり$m_{k+1}=2m_k=2k$である。$k=m_k$は$2$の冪であるから$2k$も$2$の冪である。$k<k+1$であるから$k$は$k+1$以上ではなく、$k$より大きい$2$の冪のうち最小のものは$2k$である（$k$が$2$の冪であることによる）。よって$2k$は$k+1$以上の$2$の冪のうち最小のものである。

主張 (3)を示す。第$k$操作が再確保であることは$n_{k-1}=m_{k-1}$、すなわち主張 (1)により$k-1=m_{k-1}$と同値である。$k=1$のときは$0=m_0=0$であるから成り立つ。$k\ge2$のときは$k-1\ge1$であり、主張 (2)により$m_{k-1}$は$k-1$以上の$2$の冪のうち最小のものであるから、$k-1=m_{k-1}$であることと$k-1$が$2$の冪であることは同値である。

主張 (4)を示す。$k=0$のときは$2\cdot0-0=0$である。$k\ge1$とする。主張 (2)により$m_k$は$k$以上の$2$の冪のうち最小のものである。$m_k=k$ならば$2k-m_k=k\ge0$である。$m_k>k$ならば、$m_k\ge k+1\ge2$であるから$m_k/2$も$2$の冪であり、最小性により$m_k/2<k$である。よって$m_k<2k$、すなわち$2n_k-m_k=2k-m_k>0$である。▨

証明.補題 5.2 (1)により$n_{i-1}=i-1$である。第$i$操作が再確保でなければ$c_i=1$、再確保であれば$c_i=n_{i-1}+1=i$である。よって

である。補題 5.2 (3)により、再確保が起こる添字は$i=1$と、$i-1$が$2$の冪である$i$である。$i=1$の項は$i-1=0$であるから和に寄与しない。$i-1=2^{j}$かつ$1\le i\le N$を満たす$j$は$2^{j}\le N-1$を満たす非負整数であるから、$N\ge2$のとき

である。$N=1$のときは再確保は$i=1$だけであり、和は$0$である。$N=0$のときは操作が無い。

評価を行う。$N\ge2$のとき$2^{J}\le N-1$であるから$2^{J+1}-1\le2(N-1)-1=2N-3$であり、総費用は$N+2N-3=3N-3\le3N$以下である。$N=1$のとき総費用は$1\le3$、$N=0$のとき$0\le0$である。▨

証明. 右側の不等式は補題 5.2 (4)である。左側の不等式を$k$についての帰納法で示す。

$k=0$のとき$R_0(\sigma)=0$であり$2n_0-m_0=0$であるから等号が成り立つ。

$k\ge1$とし、$R_{k-1}(\sigma)\ge2n_{k-1}-m_{k-1}$を仮定する。$R_k(\sigma)=R_{k-1}(\sigma)+3-c_k$である。三つの場合に分ける。

第$k$操作が再確保でない場合。$c_k=1$、$n_k=n_{k-1}+1$、$m_k=m_{k-1}$であるから

である。

第$k$操作が再確保であり$m_{k-1}\ge1$である場合。$n_{k-1}=m_{k-1}$であるから、$m=m_{k-1}$と置くと$c_k=m+1$、$n_k=m+1$、$m_k=2m$であり$2n_k-m_k=2(m+1)-2m=2$である。帰納法の仮定から$R_{k-1}(\sigma)\ge2m-m=m$が得られるので

である。

第$k$操作が再確保であり$m_{k-1}=0$である場合。このとき$n_{k-1}=0$であるから$k=1$であり、$c_1=1$、$D_1=(1,1)$である。$R_1(\sigma)=0+3-1=2$であり$2n_1-m_1=2-1=1$であるから$R_1(\sigma)\ge2n_1-m_1$である。