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

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

我对如何进一步进行以获得最终结果感到困惑。请帮助我解决这个问题。

- devsda

---

T是什么？它是比较次数还是时间，还是其他什么？ - Mark Byers

你究竟想要做什么？ - Wormbo

你错过了作业标签还是我们走错了方向？ - Maziar Aboualizadehbehbahani

你在尝试寻找复杂度吗？ - aioobe

@Mark ByersT 是解决这个算法所需的时间。 - devsda

Answer 1

问题在于下一个m和n的值的大小取决于前面的值，而不仅仅是它们的大小。Knuth在《计算机程序设计艺术》第2卷：半数值算法，第4.5.3节中详细解释了这一点。在大约五页的内容后，他证明了你可能已经猜到的最坏情况，即m和n是相邻的斐波那契数。从此可以得出结论（或其他方式！），最坏情况下所需的除法次数与两个参数中较大者的对数成线性关系。

经过更多深入的数学推导，Knuth证明了平均情况下所需的除法次数也与参数的对数成线性关系。

- mcdowella

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=n-m<n/2

因此，您实际上是将较大的输入减半，在两个调用中，两个参数都将被减半。

- sukunrt