計算アルゴリズム【Ⅱ】

計算アルゴリズム【Ⅱ】 at TECH

812:デフォルトの名無しさん
08/11/16 11:41:06
>>811
互除法のアルゴリズムを
gcd(a,b) = if b == 0 then return a else return gcd(b, a mod b)
として解析する（mod は割り算の余り）．a, b ≧ 0 の場合のみ考える．

補題．
a > b ≧ 0 について，gcd(a,b) が k (≧ 1) ステップで終わるならば
a ≧ 1.1^{k+1}, b ≧ 1.1^k が成立する．
証明．
k = 1 のときは自明．k-1 まで正しいと仮定．
gcd(a,b) が k ステップで終わるとき，
gcd(b, a mod b) は k-1 ステップで終わるので帰納法の仮定から
b ≧ 1.1^{k-1}, a mod b ≧ 1.1^k，したがって
a ≧ 1.1^k + 1.1^{k-1} = 1.1^{k-1}×2.1 ≧ 1.1^{k-1}×1.21 = 1.1^{k+1}．
系．
gcd(a,b) のステップ数は O(log min{a,b})．
証明．
a > b としてよく，log b = m とおけば補題より O(m) 回以下のステップ数で終わるため．

次ページ

続きを表示

1を表示