この章で言いたいことを一言でいうと、
ある問題を特にしても、アルゴリズム（解き方）が違えば、実行時間が違うよ！
ということです。
皆さんも、繰り返しや再帰を使う関数を実行していたとき、変数を大きな数にしすぎてフリーズした！なんて経験があるはず。
あれは実際、コンピュータが超ガンバって計算してるんですよ。
コンピュータだって一瞬で全ての答えを出すわけではありません。
だけど、それはつまり、
同じ答えを導くにしても、計算量が減るようにアルゴリズムを改良してやれば、より素早く答えを出せる
ということ。
教科書では、例として、フィボナッチ数を求めるアルゴリズムと、整列のアルゴリズムを照会しています。
フィボナッチ数のアルゴリズムはこちら。
その1.再帰的アルゴリズムfibr(k)→実行時間はkの指数関数に近似できる
def firb(k)
if k==0 || k==1
1
else
fibr(k-1) + fibr(k-2)
end
end
その2.数え上げアルゴリズムfibl(k)
def fibl(k)
f=1
p1=1
for i in 2..k
p2=p1
p1=f
f=p1+p2
end
f
end
その2の2.数え上げでfibの下6桁だけを求めるfibl6(k)
→実行時間はkの一次関数に近似できる
def fibl6(k)
f=1
p1=1
for i in 2..k
p2=p1
p1=f
f=(p1+p2)%/1000000
end
f
end
その3.黄金比による近似解アルゴリズムfiba(k)
def fiba(k)
phi=(1+sqrt(5))/2 ←これが黄金比
phi**(k+1)/sqrt(5)
end
これらのアルゴリズムの速さを比べるために用いられるのが、計算量とそのオーダー。
ですが、これは前期の必修科目情報の範囲なので、とばします。
詳しくは教科書P86〜89をどうぞ。
参考までに、fibr(k)はO(φ^k)、fibl(k)はO(k)です。
さらに！
その4.行列を用いたアルゴリズムfibm(k)
フィボナッチ数を、vk=( fib(k+1) , fib(k) )として考えると、2×2行列Q=[[1,1],[1,0]]をつかって、
v0=( 1 , 1 ) , vk+1=Qvk (k=0,2,3,...)
すなわち、
vk=Q^k × v0
と書けます。
行列Qのn乗計算をそのままやるとO(n)になり、数え上げプログラムと大差なくなってしまいますが、
Q = E (n=0)
(Q^(n/2))^2 (nは2以上の偶数)
Q×Q^(n-1) (nは奇数）
としてやれば、あら不思議、めっちゃ計算量が減っちゃいますね。
なんと、O(logk)になります。
def matmul(a,b) ←行列a,bの積を求める関数
c = make2d(2,2)
c[0][0] = a[0][0]*b[0][0] + a[0][1]*b[1][0]
c[0][1] = a[0][0]*b[0][1] + a[0][1]*b[1][1]
c[1][0] = a[1][0]*b[0][0] + a[1][1]*b[1][0]
c[1][1] = a[1][0]*b[0][1] + a[1][1]*b[1][1]
c
end
def matsquare(a) ←行列aの自乗を求める関数
c = make2d(2,2)
c[0][0] = a[0][0]**2 + a[0][1]*a[1][0]
c[0][1] = a[0][0]*a[0][1] + a[0][1]*a[1][1]
c[1][0] = a[1][0]*a[0][0] + a[1][1]*a[1][0]
c[1][1] = a[1][0]*b[0][1] + a[1][1]**2
c
end
def matpower(a,n) ←行列aのn乗を求める関数
if n==0
[[1,0],[0,1]]
else
if n%2==0
matsquare(matpower(a,n/2))
else
matmul(a,matpower(a,n-1))
end
end
end
def fibm(k)
q=matpower([[1,1],[1,0]],k-1)
q[0][0]+q[0][1]
end
