如何解决给定算法的递归？

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详细介绍了"计算机程序设计的艺术"第2卷:研究数学算法,第4.5.3节.大约五页之后,他证明了你可能已经猜到了,最糟糕的情况是m和n是连续的斐波纳契数.从这个(或其他!)可以看出,在最坏的情况下,所需的分割数量在两个参数中较大者的对数中是线性的.

经过大量的重型数学运算后,Knuth证明了平均情况在参数的对数中也是线性的.