07/09/29 14:28:02
>>573
a[n] = [sqrt(2*a[n-1]*(a[n-1]+1))] # []: Gauss記号
この式を見るとnが1増えると√2倍でa[n]は指数的な増加。
ソート済みk個と2個のマージは
2分探索を2回使えば2logk回。
詳しくは見てないが、2logkの係数の2が√2になりそうだし、
kが指数的に増加して比較回数が線形増加もa[n]の式とオーダーは合っている。
07/09/29 14:28:02
>>573
a[n] = [sqrt(2*a[n-1]*(a[n-1]+1))] # []: Gauss記号
この式を見るとnが1増えると√2倍でa[n]は指数的な増加。
ソート済みk個と2個のマージは
2分探索を2回使えば2logk回。
詳しくは見てないが、2logkの係数の2が√2になりそうだし、
kが指数的に増加して比較回数が線形増加もa[n]の式とオーダーは合っている。