- 574 名前：デフォルトの名無しさん mailto:sage [2007/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]の式とオーダーは合っている。
↑キャッシュ検索、類似スレ動作を修正しました、ご迷惑をお掛けしました |
計算アルゴリズム【Ⅱ】
| |
read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef