第1回レポートJane's Flower Shopの解答例を知りたい,という声をそこそこ聞いたので,解答例を以下に示す. まず問題の概要を説明し,次に解答の方針を説明し,最後にPythonによるコード例を示す.
Jane's Flower Shopを非常に簡単に説明すると,
が与えられたときに,
を出力せよ,という問題である.
説明を簡単にするため$f(r) = C_0 (1 + r)^M + C_1 (1 + r)^{M-1} + \dots + C_{M-1} (1 + r) + C_M$とする. この問題は$f(r) = 0$となる実数$r$を求めよという問題であり,解析的に解くのは難しいかもしれない. しかし,具体的に与えられた数値列$C_0, C_1, \dots, C_M$に対して$f(r) = 0$となる$r$を,コンピューターとアルゴリズムによって求めるのは困難ではない.
$r$を具体的に1つ決めれば,それが$f(r) = 0$を満たすかは,$f(r)$に代入して計算すれば簡単にわかる. よって,代入した結果の$f(r)$がプラスかマイナスかで2分探索すれば良さそうである. 2分探索は講義の最初の方で解説した. 2分探索を利用できる条件は,
ことである. 一般に,$f(r)$は$r$に関して単調に増加,あるいは減少しているとは限らない. しかし,問題の説明に「解が唯一に定まる」ことを保証する,とある. よって$f(r)$は,マイナス,ゼロ,プラスに関しては必ず単調に並んでいるはずである. よって2分探索を利用して問題ない.
ただし,与えられた数値列$C_0, C_1, \dots, C_M$次第で,$f(r)$の符号は$r$に関して「単調非増加」も「単調非減少」もありうる. よって「単調非増加」でも「単調非減少」でもどちらでも対応できるようにコーディングする必要がある.
2分探索をそのまま適用すれば良いというものではないので,アルゴリズムを理解し使いこなす(カスタマイズする)力が試される.
以上の方針のもと,Pythonでコーディングした例を以下に示す. 関数total_cash(M, C, r)は,数値列$C = C_0, C_1, \dots, C_M$と$r$を入力として$f(r)$を返す関数である. 関数solve(M, C)が問題を解いている関数であり,$r$の下界を-1,上界を1として2分探索している.
def total_cash(M, C, r):
cash = 0
rate = 1
for i in range(M, 0, -1):
cash += C[i] * rate
rate *= 1 + r
cash -= C[0] * rate
return cash
def solve(M, C):
upper_bound = 1.0
lower_bound = -1.0
while upper_bound - lower_bound > 10 ** -10:
middle = (upper_bound + lower_bound) / 2
'''
以下の条件式は少し技巧的である.
「現在の上界による左辺値と,中間による左辺値の符号が同じか否か」
で2分探索の探索範囲を変えれば良い,ということである.
'''
if total_cash(M, C, upper_bound) * total_cash(M, C, middle) > 0:
upper_bound = middle
else:
lower_bound = middle
return upper_bound
実際に,例題の数値を入力して解いてみる.
M = 2
C = [200, 100, 100]
print('%10.9f' % solve(M, C)) # 少数第9位まで表示する.
0.000000000
M = 3
C = [10000, 3000, 4000, 5000]
print('%10.9f' % solve(M, C))
0.088963395
M = 5
C = [3000, 100, 100, 100, 100, 100]
print('%10.9f' % solve(M, C))
-0.401790749
いずれも正しい出力が得られた. なお,問題の説明文にある通り,この問題の解の正誤は少数第9位までで判定される.
最後に,関数solveの時間複雑度(実行時間)を見積もる. 問題設定では計算の精度は$10^{-9}$と決められているが,一般に少数第$R$位までの精度を要求されると仮定する. また,$C_\text{max} = \max\{C_0,\dots,C_M\}$とする.
関数solveのwhile文の中は$\text{O}(\log(R))$回繰り返され,その中ではmiddleの計算やtotal_cashの計算が行われる. middleの計算は$\text{O}(R)$である. 関数total_cashの時間複雑度を$T(M, C_\text{max}, R)$とすると,関数solveの時間複雑度は$\text{O}(\log(R)(R + T(M, C_\text{max}, R))$となる.
関数total_cashのfor文の中は$\text{O}(M)$回繰り返され,そのそれぞれで最大$\log(C_\text{max})$桁の数と最大$R$桁の数の乗算が行われる. その乗算を普通の筆算と同じ要領で行うならば,時間複雑度は$\text{O}(\log(C_\text{max}) R)$である. 一方で,例えば分割統治法を用いるならば乗算の時間複雑度は$\text{O}((\max\{\log(C_\text{max}, R\})^{\log_2 3})$となる. (一般には)より速い分割統治法を用いると仮定するとtotal_cashの時間複雑度$T(M, C_\text{max}, R)$は$\text{O}(M(\max\{\log(C_\text{max}, R\})^{\log_2 3})$となる.
まとめると,関数solveの時間複雑度は$\text{O}(\log(R)(R + M(\max\{\log(C_\text{max}, R\})^{\log_2 3}))$となる. そして,本来の問題設定通り計算精度$R$を定数と見なすと$\text{O}(M (\log(C_\text{max}))^{\log_2 3}) = \text{O}(M (\log(C_\text{max}))^{1.58})$である.