在我准备算法课的期中导论时，我正在浏览教授之前发布的一些测试，我发现了一个问题：
计算gcd（312455）有两种方法：找到每个数的因式分解，并使用euclid算法。每种方法的复杂性是什么？
他的回答是：
gcd(455,312) = gcd(312,143) = gcd(143,26) = gcd(26,13) = gcd(13,0) = 13
factors(312)= {2, 3, 13} factors(455)= {5, 7, 13}
复杂性：
gcd-
log(n)因素-
sqrt(n)他是如何达到复杂性的呢？
最佳答案
要分析欧几里德GCD，必须选择最坏情况值：我个人发现斐波那契对最适合这个问题。例如。
EGCD(121393, 75025) = 1; // With 24 iterations (or recursive calls).
看看这个“序列”：
对于斐波那契对，我们注意到：
121393 % 75025 == 121393 - 75025 == 46368.
因此，存在一个
121393 / 46368 = **2.61** (more or less);当然，最坏情况下的运行时间将使用小的Oh表示法，因为最好的情况将采用ω（1），换句话说就是常数时间，例如，当被除数为1000，除数为2时。
由于我们有一个递减因子，我们可以把递归关系设为如下：
您必须知道，这个运行时间与EGCD算法的迭代版本完全相同。