我很难确定欧几里德最大公分母算法的时间复杂度是多少。这个算法的伪代码是:
function gcd(a, b)
while b ≠ 0
t := b
b := a mod b
a := t
return a
这似乎取决于a 和b。我的想法是时间复杂度是O(a % b)。那是对的吗?有更好的写法吗?
最佳答案
分析 Euclid 算法时间复杂度的一个技巧是跟踪两次迭代中发生的情况:
a', b' := a % b, b % (a % b)
现在 a 和 b 都会减少,而不是只有一个,这使得分析更容易。您可以将其分为以下情况:
- 小 A:
2a <= b
- 小 B:
2b <= a
- 小A:
2a > b
但是a < b
- 小B:
2b > a
但是b < a
- 等于:
a == b
现在我们将证明每个案例都会减少总数 a+b
至少四分之一:
- 小 A:
b % (a % b) < a
和2a <= b
, 所以b
至少减少了一半,所以a+b
至少减少了25%
- 小 B:
a % b < b
和2b <= a
, 所以a
至少减少了一半,所以a+b
至少减少了25%
- 小A:
b
将变为b-a
,小于b/2
,递减a+b
至少25%
. - 小B:
a
将变为a-b
,小于a/2
,递减a+b
至少25%
. - 等于:
a+b
下降到0
, 明显减少a+b
至少25%
.
因此,通过案例分析,每双步递减a+b
至少 25%
.在 a+b
之前,这可能发生的次数最多被迫跌破1
.到达 0 之前的总步数 (S
) 必须满足 (4/3)^S <= A+B
.现在开始吧:
(4/3)^S <= A+B
S <= lg[4/3](A+B)
S is O(lg[4/3](A+B))
S is O(lg(A+B))
S is O(lg(A*B)) //because A*B asymptotically greater than A+B
S is O(lg(A)+lg(B))
//Input size N is lg(A) + lg(B)
S is O(N)
因此迭代次数与输入数字的数量成线性关系。对于适合 cpu 寄存器的数字,合理的做法是将迭代建模为采用常数时间并假装 gcd 的总运行时间是线性的。
当然,如果您要处理大整数,则必须考虑到每次迭代中的模数运算的成本不是恒定的。粗略地说,总的渐近运行时间将是多对数因子的 n^2 倍。 Something like n^2 lg(n) 2^O(log* n)
.可以通过使用 binary gcd 来避免多对数因子。 .
关于algorithm - 欧几里德算法的时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3980416/