GCD代码的时间复杂度

Question

我正在尝试了解以下代码的时间复杂度：

int gcd(int n, int m) {
   if (n%m ==0) return m;
   if (n < m) swap(n, m);
   while (m > 0) {
       n = n%m;
       swap(n, m);
   }
   return n;
}

我读到上面代码的复杂度是？（logn）。有人可以向我解释其背后的逻辑吗？

Answer 1

考虑算法的任何两个步骤。

在某些时候，您可以得到具有> a的数字（a，b）。在第一步之后，将它们转到（b，c），其中c = a mod b，而在第二步之后，这两个数字将是（c，d），其中d = b mod c。

现在回想一下。由于d = b mod c，我们知道对于某些k> 0，b = kc + d。最小的可能性是k = 1，因此b？1c + d = c + d。

从该结果和a> b得到a> c + d。如果我们加上刚得出的最后两个不等式，则得出（a + b）> 2（c + d）。换句话说，在每两个连续步骤之后，两个数字的总和减小到小于其原始大小的一半。

现在来看算法的第一步。一开始，我们有一些（a，b）的a> b。在第一步之后，我们有（b，c），其中c = a mod b，显然b> c。因此，在第一步之后，两个数字最多等于两个输入数字中的较小者。

将这两个结果放在一起，我们可以得出结论，迭代次数（在其他实现中为递归调用）在较小的输入数中最多为对数。换句话说，迭代次数在较小的输入number中的位数中最多是线性的。