前提・実現したいこと
ユークリッドの互除法を再帰表現ありとなしの時間計算量(オーダー)を明らかにしようとしています。
gcd(1071, 1029)
の例で以下のプログラムを実行して繰り返し回数を表示しました。
発生している問題・エラーメッセージ
以下が出力結果ですが、今回の場合は再帰ありで4回、再帰なしで3回の繰り返しでした。
オーダ記法で表すには、条件分岐の部分に着目する必要がありますが、再帰なしのwhile y > 0
再帰ありのif y == 0
で、どちらもyに依存するので、時間計算量は0(C)
(Cは定数)となると考えました。
しかし、それではなぜ再帰で定義する必要があるのかわからず、
・再帰表現ありとなしの時間計算量(オーダー)
・再帰表現ありとなしのメリット、デメリット
の2点について教えていただきたいです。
再帰表現あり
else conditional else conditional else conditional if conditional 21
再帰表現なし
culc culc culc 21
該当のソースコード
再帰表現あり
def gcd(x, y): if y == 0: print("if conditional") return x else: print("else conditional") return gcd(y, x % y) #再帰 print(gcd(1071, 1029))
再帰表現なし
Python
1def gcd(x, y): 2 while y > 0: 3 print('culc') 4 a = y 5 y = x % y 6 x = a 7 return x 8 9print(gcd(1071, 1029))
補足情報(FW/ツールのバージョンなど)
python3.6
回答1件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
退会済みユーザー
2019/07/07 02:24
2019/08/04 00:32 編集