超简单GCD的时间复杂度

Question

当我需要计算两个整数的最大公约数时，我有时会使用这种超级简单的算法，而不是使用欧几里得算法或二元GCD算法：

// Given 0<A<B, calculate GCD(A,B)
unsigned gcd = A;
for (unsigned r = B%gcd; r>0; gcd=r, r = B%gcd);

在某些情况下，我觉得内联编写而不是在某处定义函数是可以的。 当 GCD 计算的时间被其他事情淹没时，即使需要很多步骤，我也会使用它。

但是，通过实验，这可以采取的步骤数似乎比 log₂ B: https://ideone.com/SVRa64

增长得快一点

有人能证明紧界吗？

Answer 1

在担心运行时之前，您可能需要先查看正确性，因为您的代码认为 3 和 8 的最大公约数是 2：首先，它计算 8 % 3 并得到 2，然后它计算 8 % 2，得到 0 ，并以 gcd = 2 退出循环。但是 2 不能整除 3 ...

解决此问题的明显方法是进行交换。那么你就有了欧几里得算法，并且可以依赖众所周知的其对数运行时间的证明。