[[院試勉強会]]
http://www.i.u-tokyo.ac.jp/edu/course/mi/admission.shtml~
http://www.i.u-tokyo.ac.jp/edu/course/mi/pdf/2005suuri-j.pdf~
- 第1問~
時間&imgtex($t$);の関数&imgtex($y_1,y_2,y_3$);に関する微分方程式~
&imgtex(\begin{align*}\frac{d}{dt}\begin{pmatrix}y_1\\y_2\\y_3\end{pmatrix}&=\begin{pmatrix}0&y_3/I_3&-y_2/I_2\\-y_3/I_3&0&y_1/I_1\\y_2/I_2&-y_1/I_1&0\end{pmatrix}\begin{pmatrix}y_1\\y_2\\y_3\end{pmatrix}\tag{*}\end{align*});
を考える．ただし，&imgtex($I_1,I_2,I_3$);は正の定数とする．
--(1)方程式(*)が，次の二つの保存量を持つことを示せ．~
&imgtex(\begin{align*}L=y_1^2+y_2^2+y_3^2,\ K=\frac{1}{2}\left(\frac{y_1^2}{I_1}+\frac{y_2^2}{I_2}+\frac{y_3^2}{I_3}\right).\end{align*});~
---微分して0になることを示せばよい．~
&imgtex(\begin{align*}\frac{dL}{dt}&=2\left(y_1\frac{dy_1}{dt}+y_2\frac{dy_2}{dt}+y_3\frac{dy_3}{dt}\right)\\&=2\left(\frac{y_1y_3}{I_3}-\frac{y_1y_2}{I_2}-\frac{y_2y_3}{I_3}+\frac{y_2y_1}{I_1}+\frac{y_3y_2}{I_2}-\frac{y_3y_1}{I_1}\right)=0\end{align*});~
&imgtex(\begin{align*}\frac{dK}{dt}&=\frac{y_1}{I_1}\frac{dy_1}{dt}+\frac{y_2}{I_2}\frac{dy_2}{dt}+\frac{y_3}{I_3}\frac{dy_3}{dt}\\&=\frac{y_1y_3}{I_1I_3}-\frac{y_1y_2}{I_1I_2}-\frac{y_2y_3}{I_2I_3}+\frac{y_2y_1}{I_2I_1}+\frac{y_3y_2}{I_3I_2}-\frac{y_3y_1}{I_3I_1}=0\end{align*});
--一般に，時間&imgtex($t$);の関数&imgtex($\bm{z}=(z_1,z_2,\dots,z_m)^{\top}$);に関する微分方程式~
&imgtex(\begin{align*}\frac{d\bm{z}}{dt}=\bm{f}(\bm{z})\tag{**}\end{align*});~
に対して，差分方程式~
&imgtex(\begin{align*}\frac{\bm{z}^{(n+1)-\bm{z}^{(n)}}}{h}=\bm{f}\left(\frac{\bm{z}^{(n+1)+\bm{z}^{(n)}}}{2}\right)\end{align*});~
を陰的中点則による離散化方程式という．
ここで，&imgtex($h>0$);は時間の離散化幅を表し，
&imgtex($\bm{z}^{(n)}$);は&imgtex($\bm{z}(nh)$);の近似である．
--(2)方程式(*)を陰的中点則で離散化した方程式においても，
(1)の&imgtex($L,K$);が保存量であることを示せ．
---(3)より明らか.
--(3)方程式(**)において2次形式&imgtex($\bm{z}^{\top}C\bm{z}$);（ただし，&imgtex($C$);は対称行列）が保存量であるとき，
陰的中点則による離散化方程式においても，
&imgtex($\bm{z}^{\top}C\bm{z}$);が保存量であることを示せ．
---&imgtex($\bm{z}^{\top}C\bm{z}$);が保存量であるので，~
&imgtex(\begin{align*}\frac{d}{dt}(\bm{z}^{\top}C\bm{z})=2\bm{z}^{\top}Cf(\bm{z}).\end{align*});~
&imgtex($\bm{z}$);に&imgtex($\frac{\bm{z}^{(n+1)}+\bm{z}^{(n)}}{2}$);を代入して，~
&imgtex(\[2\frac{\bm{z}^{(n+1)}+\bm{z}^{(n)}}{2}C\bm{f}\left(\frac{\bm{z}^{(n+1)}+\bm{z}^{(n)}}{2}\right)=(\bm{z}^{(n+1)}+\bm{z}^{(n)})C\left(\frac{\bm{z}^{(n+1)}-\bm{z}^{(n)}}{h}\right)=0\]);~
これを，&imgtex($h$);倍して展開すれば，&imgtex($C$);は対称行列なので，~
&imgtex(\[(\bm{z}^{(n+1)})^{\top}C z^{(n+1)}=(\bm{z}^{(n)})^{\top}C z^{(n)}.\]);
----
-第2問~
平面&imgtex($\mathbb{R}^2$);から&imgtex($\mathbb{R}^2$);への滑らかな写像&imgtex($T$);を以下のように表す．~
&imgtex(\begin{align*}T:\begin{pmatrix}x\\y\end{pmatrix}\mapsto\begin{pmatrix}f(x,y)\\ g(x,y)\end{pmatrix}.\end{align*});~
&imgtex(\begin{align*}T\begin{pmatrix}\bar{x}\\ \bar{y}\end{pmatrix}=\begin{pmatrix}\bar{x}\\ \bar{y}\end{pmatrix}\end{align*});を満たす
&imgtex(\begin{align*}\begin{pmatrix}\bar{x}\\ \bar{y}\end{pmatrix}\end{align*});を不動点という．
また，不動点&imgtex(\begin{align*}\bar{x}\\ \bar{y}\end{align*});における写像&imgtex($T$);の固有値の絶対値がすべて1より小さいとき漸近安定，
そうでないとき不安定であるという．
--(1)ヤコビ行列&imgtex($J(\bar{x},\bar{y})$);の行列式&imgtex($\det J(\bar{x},\bar{y})$);を横軸，トレース&imgtex($\mathrm{tr} J(\bar{x},\bar{y})$);を縦軸とする平面において,不動点が漸近安定である領域を図示せよ．
---簡単のため行列式を&imgtex($d$);，トレースを&imgtex($t$);と書くことにする．
すると，固有値&imgtex($\lambda$);は&imgtex($f(\lambda)=\lambda^2-t \lambda+d=0$);を満たす．~
判別式&imgtex($t^2-4d\ge 0$);のとき，&imgtex($-1<t/2<1,\ f(1)> 0,\ f(-1)> 0$);．~
判別式&imgtex($t^2-4d< 0$);のとき，&imgtex($|\lambda_1|=|\lambda_2|,\ |d|=|\lambda_1\lambda_2|=|\lambda|< 1$);．~
よって，&imgtex($d<1, d>|t|-1$);の三角形の内部が求める領域．
--(2)&imgtex($f(x,y)=-ax^2+y+1,\ g(x,y)=bx$);であるとき，
写像&imgtex($T$);をエノン写像という．
エノン写像の不動点を求めよ．
また，求めた不動点の安定性とパラメータの値とtの関係を調べて，その結果を&imgtex($b$);を横軸，&imgtex($a$);縦軸とするパラメータ平面上に図示せよ．
---不動点は，~
&imgtex(\begin{align*}\bar{x}&=-a\bar{x}^2+\bar{y}+1\\\bar{y}&=b\bar{x}\end{align*});~
を満たすので，これを解いて~
&imgtex(\begin{align*}\bar{x}&=\frac{b-1\pm\sqrt{(1-b)^2+4a}}{2a},\\\bar{y}&=b\frac{b-1\pm\sqrt{(1-b)^2+4a}}{2a}.\end{align*});~
&imgtex(\begin{align*}J=\begin{pmatrix}-2a\bar{x}&1\\b&0\end{pmatrix}\end{align*});~
これより，~
&imgtex(\begin{align*}\mathrm{tr} J&=-2a\bar{x}=1-b\pm\sqrt{(1-b)^2+4a}\\\det J&=-b\end{align*});~
これが，(1)で求めた三角形の領域に入れば良い．
&imgtex($1-b=b'$);とおくと，
&imgtex($0<b'<2$);,&imgtex($b'> |b'\pm\sqrt{b'^2+4a}|=\pm b'+\sqrt{b'^2+4a}$);．~
不動点は実なので&imgtex($b'^2+4a\ge 0$);~
複号が＋のときは，&imgtex($0>\sqrt{b'^2+4a}$);となり漸近安定領域はない．~
－のときは，&imgtex($2b'>\sqrt{b'^2+4a},\ 3(1-b)^2>4a$);．~
これと&imgtex($a,b\ne 0$);を条件とすればよい.
--(3)エノン写像&imgtex($T$);を，非線型写像&imgtex($T_1$);，線型写像&imgtex(\begin{align*}T_2:\begin{pmatrix}x\\ y\end{pmatrix}\mapsto\begin{pmatrix}b&0\\0&1\end{pmatrix}\begin{pmatrix}x\\y\end{pmatrix}\end{align*});，および線型写像&imgtex(\begin{align*}T_3:\begin{pmatrix}x\\y\end{pmatrix}\mapsto\begin{pmatrix}0&1\\1&0\end{pmatrix}\begin{pmatrix}x\\y\end{pmatrix}\end{align*});の合成によって~
&imgtex(\begin{align*}T\begin{pmatrix}x\\ y\end{pmatrix}=T_3\left(T_2\left(T_1\begin{pmatrix}x\\ y\end{pmatrix}\right)\right)\end{align*});~
と表すとき，&imgtex(\begin{align*}T_1\begin{pmatrix}x\\y\end{pmatrix}\end{align*});を具体的に求めよ．
また，&imgtex($a=1.4, b=0.3$);であるとき，長方形領域が&imgtex($A$);が順次変換された領域&imgtex($T_1(A), T_2(T_1(A)), T_3(T_2(T_1(A)))$);を図示するとともに，
その面積を求めよ．
--- ~
&imgtex(\begin{align*}\begin{pmatrix}-ax^2+y+1\\ bx\end{pmatrix}&=\begin{pmatrix}0&1\\1&0\end{pmatrix}\begin{pmatrix}b&0\\0&1\end{pmatrix}T_1\begin{pmatrix}x\\y\end{pmatrix}\\&=\begin{pmatrix}0&1\\ b&0\end{pmatrix}T_1\begin{pmatrix}x\\y\end{pmatrix}\end{align*});~
より，~
&imgtex(\begin{align*}T_1\begin{pmatrix}x\\y\end{pmatrix}=\begin{pmatrix}x\\-ax^2+y+1\end{pmatrix}.\end{align*});~
これより，&imgtex($T_1(A)$);は&imgtex(\begin{align*}\left\{\left.\begin{pmatrix}x\\-1.4x^2+y+1\end{pmatrix}\right|-1\le x\le 1,\ -0.1\le y\le 0.1\right\}\end{align*});なので，面積は&imgtex($(1-(-1))\times(0.1-(-0.1))=0.4$);．~
&imgtex($T_2(T_1(A))$);は&imgtex($x$);軸方向に&imgtex($0.3$);倍したものなので，面積は&imgtex($0.4\times 0.3=0.12$);．~
&imgtex($T_3(T_2(T_1(A)))$);は&imgtex($x$);軸&imgtex($y$);軸を入れ替えたものなので，面積は&imgtex($0.12$);．
--(4)エノン写像&imgtex($T$);が&imgtex($\mathrm{R}^2$);から&imgtex($\mathrm{R}^2$);の上への1対1写像であることを示せ．
---逆写像は&imgtex(\begin{align*}\begin{pmatrix}x/b\\ay^2/b^2-1+x\end{pmatrix}\end{align*});であり，どちらも全域で定義されていることは明らかなので，1対1社増となっている．
----
- 第3問~
ある物体の重さ&imgtex($\mu$);を測定する実験を2回行って得られる観測値を&imgtex($X_1,X_2$);とし，
その標本平均を&imgtex($\bar{X}=(X_1+X_2)/2$);とする．
測定の誤差&imgtex($X_1-\mu, X_2-\mu$);は独立に平均0，分散1の正規分布に従うものとする．
--(1)&imgtex($Y=(X_1-X_2)/2$);とおく．&imgtex($\bar{X}$);と&imgtex($Y$);との同時確率分布を求めよ．
---確率密度関数をそれぞれ&imgtex($f_{X_1},f_{X_2},f_{\bar{X}},f_Y$);などとおくことにすると，~
&imgtex(\begin{align*}f_{X_1}(x)&=\frac{1}{\sqrt{2\pi}}e^{-(x-\mu)^2/2}\\f_{X_2}(x)&=\frac{1}{\sqrt{2\pi}}e^{-(x-\mu)^2/2}\\f_{X_1X_2}(x_1,x_2)&=\frac{1}{2\pi}e^{-((x_1-\mu)^2+(x_2-\mu)^2)/2}\end{align*});~
これを&imgtex($\bar{X},Y$);に変数変換すると，~
&imgtex(\begin{align*}f_{\bar{X}Y}(\bar{x},y)&=\frac{1}{2\pi}e^{-((\bar{x}+y-\mu)^2+(\bar{x}-y-\mu)^2)/2}\cdot 2\\&=\frac{1}{\pi}e^{-(\bar{x}-\mu)^2-y^2}\\f_{\bar{X}}&=\frac{1}{\sqrt{\pi}}e^{-(\bar{x}-\mu)^2}\\f_{Y}&=\frac{1}{\sqrt{\pi}}e^{-y^2}\end{align*});~
--(2)標本平均&imgtex($\bar{X}$);が与えられたもとでの&imgtex($X_1$);の条件付期待値&imgtex($E[X_1|\bar{X}]$);を求めよ．
また，&imgtex($E[X_1|\bar{X}]$);の期待値と分散を求めよ．
---
&imgtex(\begin{align*}f_{X_1|\bar{X}}(x_1,\bar{x})&=\frac{f_{X_1\bar{X}}(x_1,\bar{x})}{f_{\bar{X}}(\bar{x})}\\&=\frac{f_{\bar{X}Y}(\bar{x},x_1-\bar{x})}{f_{\bar{X}}(\bar{x})}\\&=\frac{f_{\bar{X}}(\bar{x})f_{Y}(x_1-\bar{x})}{f_{\bar{X}}(\bar{x})}\\&=f_{Y}(x_1-\bar{x})\\&=\frac{1}{\sqrt{\pi}}e^{-(x_1-\bar{x})^2}\end{align*});~
これより，&imgtex($E[X_1|\bar{X}]=\bar{x}$);．~
また，&imgtex($f_{\bar{X}}(\bar{x})=\frac{1}{\sqrt{\pi}}e^{-(\bar{x}-\mu)^2}$);
なので，平均&imgtex($\mu$);分散&imgtex($1/2$);である．
--(3)&imgtex($X_1,X_2$);の関数&imgtex($f(X_1,X_2)$);を考える．
&imgtex($\bar{X}$);が与えられたもとでの&imgtex($f(X_1,X_2)$);の条件付期待値&imgtex($E[f(X_1,X_2)|\bar{X}]$);は&imgtex($\mu$);に依存しない&imgtex($\bar{X}$);の関数であることを示せ．
---&imgtex($E[f(X_1,X_2)|\bar{X}]=\int_{-\infty}^{\infty}f(\bar{x}+y,\bar{x}-y)f_Y(y)dy$);と書けるので，&imgtex($\mu$);に依存しない&imgtex($\bar{X}$);の関数である．
--(4)&imgtex($f(X_1,X_2)$);が&imgtex($\mu$);の不偏推定量であるとき，
&imgtex($E[f(X_1,X_2)|\bar{X}]$);は&imgtex($\mu$);の不偏推定量となることを示せ．
また，&imgtex($E[f(X_1,X_2)|\bar{X}]$);の分散は&imgtex($f(X_1,X_2)$);の分散以下であることを示せ．
---&imgtex($f(X_1,X_2)$);が&imgtex($\mu$);の不偏推定量であるので，~
&imgtex(\begin{align*}\int_{-\infty}^{\infty}f(x_1,x_2)\frac{1}{2\pi}e^{-((x_1-\mu)^2+(x_2-\mu)^2)/2}dx_1dx_2=\mu.\end{align*});~
よって，~
&imgtex(\begin{align*}E[E[f(X_1,X_2)|\bar{X}]]&=E[\int_{-\infty}^{\infty}f(\bar{x}+y,\bar{x}-y)\frac{1}{\sqrt{\pi}}e^{-y^2}dy]\\&=\int_{-\infty}^{\infty}\int_{-\infty}^{\infty}f(\bar{x}+y,\bar{x}-y)\frac{1}{\sqrt{\pi}}e^{-y^2}\frac{1}{\sqrt{\pi}}e^{-(\bar{x}-\mu)^2}d\bar{x}dy\\&=\int_{-\infty}^{\infty}\int_{-\infty}^{\infty}f(x_1,x_2)\frac{1}{2\pi}e^{-(x-\mu)^2-(x_2-\mu)^2}dx_1dx_2=\mu.\end{align*});~
上と同様の議論により&imgtex($E[E[Y|X]]=E[Y]$);がなりたつので（繰り返しの公式），~
&imgtex(\newcommand{\Var}{\mathrm{Var}}\begin{align*}\Var[f(X_1,X_2)]-\Var[E[f(X_1,X_2)|\bar{X}]]&=(E[f^2(X_1,X_2)]^2-\mu^2)-(E[E[f(X_1,X_2)|\bar{X}]^2]-\mu^2)\\&=E[E[f^2(X_1,X_2)|\bar{X}]^2]-E[E[f(X_1,X_2)|\bar{X})]^2]\\&=E[E[f^2(X_1,X_2)|\bar{X}]^2-E[f(X_1,X_2)|\bar{X}]^2]\\&=E[\Var[f(X_1,X_2)|\bar{X}]]\ge 0.\end{align*});
--(5)十分統計量とはどのような概念か，また，どのような性質をもつか，を簡単に説明せよ．
---十分統計量とは，パラメータ&imgtex($\theta$);を持つモデルに対し，その統計量を与えたときの条件付確率分布が&imgtex($\theta$);によらないことを言う．~
（なに書けばいいのかわかりません）
----
-第4問~
&imgtex($k$);個の&imgtex($n$);次元ベクトル&imgtex($\bm{a}_1,\bm{a}_2,\dots,\bm{a}_k\in \mathbb{R}^n$);と，その添え字の集合&imgtex($K=\{1,2,\dots,k\}$);の部分集合&imgtex($L$);に対して~
&imgtex(\[C(L)=\{\bm{x}\in\mathbb{R}^n|\bm{a}_i^{\top}\bm{x}<0(\forall i\in L),\ \mathbb{a}_j^{\top}\bm{x}>0\ (\forall j\in K\setminus L)\}\]);~
と定義する．ただし，&imgtex($\bm{a}_i^{\top}$);は&imgtex($\bm{a}_i$);の転置を表し，&imgtex($K\setminus L$);は&imgtex($L$);に含まれない要素の集合を表す．
--&imgtex($k=3, n=2, \bm{a}_1=\begin{pmatrix}1\\0\end{pmatrix}, \bm{a}_2=\begin{pmatrix}1\\1\end{pmatrix},\bm{a}_3=\begin{pmatrix}-1\\1\end{pmatrix}$);としたとき，&imgtex($K=\{1,2,3\}$);の部分集合&imgtex($L$);で&imgtex($C(L)$);が非空となるものを全て書き出せ．
---全ての場合&imgtex($2^3=8$);通りを考える．~
&imgtex(\begin{align*}C(K)&\ni \begin{pmatrix}-1\\-2\end{pmatrix}&C(\emptyset)\ni\begin{pmatrix}1\\2\end{pmatrix}\\C(\{1\})&\ni\begin{pmatrix}-1\\2\end{pmatrix}&C(\{2,3\})&\ni\begin{pmatrix}1\\-2\end{pmatrix}\\C(\{3\})&\ni\begin{pmatrix}1\\0\end{pmatrix}&C(\{1,2\})&\ni\begin{pmatrix}-1\\0\end{pmatrix}\end{align*});~
ところが，&imgtex($C(\{2\}),C(\{1,3\})$);については，~
&imgtex(\begin{align*}x_1&\lessgtr 0\tag{1}\\x_1+x_2&\gtrless 0\tag{2}\\-x_1+x_2&\lessgtr 0\tag{3}\end{align*});~
であるが，&imgtex($2\times \mathrm{(1)}+\mathrm{(3)}$);より，&imgtex($x_1+x_2\lessgtr 0$);なので(2)と矛盾するので&imgtex($C(L)$);は空となる．
--(2) &imgtex($n=3$);とする．
&imgtex($C(L)$);が非空となる&imgtex($L$);の個数を&imgtex($l(\bm{a}_1,\bm{a}_2,\dots,\bm{a}_k)$);と書き&imgtex($\bm{a}_1,\bm{a}_2,\dots ,\bm{a}_k$);を動かしたときのその最大値を&imgtex($r_k=\max_{\bm{a}_1,\dots,\bm{a}_k}l(\bm{a}_1,\dots \bm{a}_k)$);とする．
&imgtex($r_1,r_2,\dots ,r_5$);の値を求めよ．また，&imgtex($r_k$);を&imgtex($k$);の関数として表せ．
---
//&imgtex($\bm{a}_k=\begin{pmatrix}1\\k\\k^2\end{pmatrix}$);とすれば，どの三つのベクトルも線型独立にとることができる（c.f. Vandermondeの行列式）．
&imgtex($\bm{a}_i^{\top}\bm{x}\gtrless 0$);は原点を通る平面で空間を切った半分を表すので，&imgtex($r_k$);は原点を通る&imgtex($k$);枚の平面で空間を分割したときの空間の数の最大値になる．~
よって，1枚増えるごとに空間の増え方が2増えるので，&imgtex($r_1=2,\ r_2=4,\ r_3=8,\ r_4=14,\ r_5=22.$);~
&imgtex($r_k=r_{k-1}+2(k-1)=\dots =r_1+\sum_{i=1}^{k-1}2i=2+2\frac{k(k-1)}{2}=k^2-k+2.$);
--(3)任意の&imgtex($L\subseteq K$);に対して&imgtex($C(L)$);が非空であるならば，
&imgtex($\{\bm{a}_1,\bm{a}_2,\dots,\bm{a}_k\}$);は線型独立であることを示せ．
---背理法で示す．
&imgtex($\bm{a}_1,\bm{a}_2,\dots,\bm{a}_k$);が線型独立ではないとする．すると一般性を失わず，ある&imgtex($w_i$);が存在して，&imgtex($a_k=\sum_{i=1}^{k-1}w_ia_i$);と表せたとしてよい．
すると，&imgtex($\bm{x}^{\top}\bm{a}_k=\sum_{i=1}^{k-1}w_i \bm{x}\bm{a}_i$);となる．ここで，&imgtex($w_i\ge 0$);ならば&imgtex($\bm{a}_i\not\in L$);，&imgtex($w_i<0$);ならば&imgtex($\bm{a}_i\in L$);とし，&imgtex($\bm{a}_k\not\in L$);とすれば右辺は正，左辺は負となり任意の&imgtex($C(L)$);が非空であることに矛盾．よって題意は示された．
--&imgtex($\{\bm{a}_1,\bm{a}_2,\dots,\bm{a}_k\}$);が線型独立であるならば，任意の&imgtex($L\subseteq K$);に対して&imgtex($C(L)$);が非空であることを示せ．
---&imgtex($\{\bm{x}\bm{a}_1,\bm{x}\bm{a}_2,\dots,\bm{x}\bm{a}_k\}$);の値を任意に変えることができるので明らか．~
c.f. http://www.orsj.or.jp/~wiki/wiki/index.php/%E3%82%A2%E3%83%AC%E3%83%B3%E3%82%B8%E3%83%A1%E3%83%B3%E3%83%88
----
- 第5問~
&imgtex($m$);と&imgtex($n$);を正整数とし，
&imgtex($m$);は&imgtex($n$);に比べて十分小さいとする．
&imgtex($M$);を&imgtex($m$);個のシンボルの集合とする．
大きさ&imgtex($n$);の1次元配列&imgtex($a$);のそれぞれの要素&imgtex($a[i]$);には，
1つのシンボルが格納されている．
配列&imgtex($a$);の中には&imgtex($m$);個のシンボルが全て現れ，
さらに同じシンボルはその全てが連続して現れる．
このとき，全ての変化位置&imgtex($m-1$);個を求める時間複雑度&imgtex($O(n)$);より小さいアルゴリズムを構成し，そのアルゴリズムの振る舞いと正しさを説明するとともに，
その時間複雑度を評価せよ．
---少々無駄があるが，要請を満たす説明のしやすいアルゴリズムを採用する．
---&imgtex($a[n]$);のシンボルを調べ，そのシンボルの切れ目をバイナリサーチで探索する．この時間計算量は&imgtex($O(\log n)$);である．~
ここで，&imgtex($a[k_{m-1}]\ne a[n],\ a[k_{m-1}+1]=a[n]$);だとすると，
&imgtex($a$);の0から&imgtex($k_{m-1}$);までの配列に対して同様の操作をすればよい．~
これを&imgtex($m-1$);回繰り返すので，時間複雑度は&imgtex($O(m\log n)$);である．
---それぞれのシンボルの探索を同時にやるようにすれば&imgtex($O(m\log(n/m))$);になると思うが時間計算量の見積もりが難しい．
-----------------
コメント
- 1-1 どちらもy1y2y3のになるはずです…これくらいあとから読む人でも分かるでしょ -- [[tako]] &new{2008-08-23 (土) 23:46:08};
- 4-(2)ですが、nの値は関係ないのでしょうか？関係ある気がするんですが…例えばn=1でaiが+,+,-の数だった時、L={1,2}かL={3}しかないですよね。おおすじは間違っているように見えないので、もうちょっと何か考えないといけない気がします。 -- [[tako]] &new{2008-08-24 (日) 15:53:57};
- m log(n/m)もm(log n - log m)でm log nにはならない？同時にやったり、過去に探索した結果を使えば、もちろん有意にはやいですけど。 -- [[tako]] &new{2008-08-24 (日) 16:24:52};
- 4-(2)はn=3なので3次元の平面分割になってます．5は&imgtex($O(m\log(n/m))=O((1-\alpha)m\log n)$);なので...オーダーは一緒でしたね． -- [[yambi]] &new{2008-08-24 (日) 17:28:14};
- il24Yf <a href="http://duuenirgntcz.com/">duuenirgntcz</a>, [url=http://uvddkegihptb.com/]uvddkegihptb[/url], [link=http://xbecsunsyksa.com/]xbecsunsyksa[/link], http://xteqmbihjdzv.com/ -- [[irlcrufrpls]] &new{2010-02-26 (金) 00:03:59};
- m25pDw <a href="http://gxqhwyuyxtxp.com/">gxqhwyuyxtxp</a>, [url=http://qmisecsnjemm.com/]qmisecsnjemm[/url], [link=http://iibmylhkquce.com/]iibmylhkquce[/link], http://pvxdngpgdcqf.com/ -- [[fysfsgvzh]] &new{2010-02-26 (金) 00:04:14};
#comment
//#comment
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
