折りたたみを展開する

おぼえ書き、まとめ、発表など

分割方法で発散を抑える

 

前回の記事の続きである。

 

 

 

be-dazzled.hatenablog.com

 

f:id:Rlan:20170608174109p:plain

 

効率性について

 

効率性と言っても、色々ある。ここでは、  n  の増加に対して、線形の場合よりも緩やかに増加する調べ方を目標にする。やや厳密に表現すると、探す時間を time(n) という  nの関数と考えたとき、 \lim_{n \rightarrow \infty} \frac{time(n)}{n} = 0 となるような調べ方である。

 

言い換えると、毒を1錠目だけの場合から初めて、  n 錠目まで増やしていく調べ方と比べて効率的な方法を目指す。この時、最悪のケースでは  n 錠まで毒を飲むので、調べ方にかかる時間は  O(n) である。

 

考え方

 

考え方は簡単である。1からn までの数直線の分割方法を考えれば良い。例えば、分割1つ当たりが g(n) となれば、最悪のケースで  (n-1)g(n) + (g(n)-1)  = ng(n) - 1 時間かかる。あとは、 g(n) n に関して、線形以下のスピードで発散すれば良い。 以上の点から、答えは以下になる。

 

答え

 

 \sqrt{n}錠ステップづつ毒を飲んでいき、毒が作用した m ステップで1回解毒剤を飲む。そして、 m-1 ステップに戻り今度は m-1 から順に1錠づつ毒を飲んでいく mステップまでに毒が作用するので、その時に最後の解毒剤を飲む。

 

 

以上めでたしめでたし。