質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

再帰

情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。

Q&A

解決済

1回答

3668閲覧

ユークリッドの互除法を再帰表現ありとなしの時間計算量(オーダー)について

退会済みユーザー

退会済みユーザー

総合スコア0

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

再帰

情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。

0グッド

1クリップ

投稿2019/07/07 01:25

前提・実現したいこと

ユークリッドの互除法を再帰表現ありとなしの時間計算量(オーダー)を明らかにしようとしています。
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

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

1つ訂正をするなら、「再帰表現あり」の方で4回と言っていますが、最後のif conditionalは再帰していないので、回数にカウントしないのが妥当と思われます。

また、オーダーの考え方が間違っています。入力の大きさに対して実行時間がどれだけ影響を受けるか、というのがオーダーの考え方で、これがyだけに依存するわけがありません。yは剰余なのですから。

本題ですが、今回のような再帰呼び出しが関数の最後に位置する再帰は「末尾再帰」と呼び、一般に単純なループに簡単に書き換えることができます。つまり2つがやっていることは本質的に全く変わりがありません。当然オーダーも変わりません。

再帰で書くメリット、というか理由としては、最大公約数を求める際に使う「互除法の原理」、つまり

2つの正の整数a,bに対し、aをbで割った余りをrとしたとき、
aとbの最大公約数は、bとrの最大公約数に等しい

ということをコード上で明示的にできるということだと思います。

投稿2019/07/07 01:59

swordone

総合スコア20649

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

退会済みユーザー

退会済みユーザー

2019/07/07 02:24

ご回答いただきましてありがとうございます。結論としてオーダ記法だとユークリッドの互除法はO()のカッコ内はどのように書けるのでしょうか
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問