algorithm - 与えられたアルゴリズムの再帰を解く方法は?

Question

int gcd(n,m)
{
  if (n%m ==0) return m;
  n = n%m;
  return gcd(m,n);
}

私はこれを解決し、私は得ました

T(n, m) = 1 + T(m, n%m)  if n > m
        = 1 + T(m, n)    if n < m
        = m              if n%m == 0

最終結果を得るためにさらに進む方法がわかりません。これを解決するのを手伝ってください。

Answer 1

ここでの問題は、m と n の次の値のサイズが、それらのサイズだけでなく、前の値が何であったかに正確に依存することです。これについては、Knuth が「The Art of Computer Programming」Vol 2: Seminumerical algorithm、セクション 4.5.3 で詳しく説明しています。約 5 ページの後、彼は、m と n が連続するフィボナッチ数である場合が最悪のケースであるという、あなたが推測したことを証明します。このことから (または別の方法で!)、最悪の場合、必要な分割数は 2 つの引数のうち大きい方の対数で線形になることがわかります。

クヌースは、かなり厳しい数学を行った後、平均的なケースが引数の対数でも線形であることを証明します。

Answer 2

mcdowella はこれに対して完璧な答えを出しています。

直感的に説明するには、次のように考えることができます。

n >= m の場合、n mod m < n/2;

これは、次のように示すことができます。

m < n/2 の場合: n mod m < m < n/2

m > n/2 の場合: n mod m = nm < n/2

したがって、実質的に大きな入力を半分にすることになり、2 回の呼び出しで両方の引数が半分になります。