GCD - 欧几里德算法和分解算法分析

Question

正如我在准备我的算法导论类期中考试，我准备，虽然以前的一些测试教授发布，我发现这样一个问题：

计算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)

他是如何到达的复杂性？

Answer 1

给定的复杂性是粗糙的最坏情况界需要的算术运算次数：

• 欧几里德算法：对于a >= b我们gcd(a,b) = gcd(b, a mod b)其中min(b, a mod b) < a/2，所以最多两个削减步骤后，我们至少有一个第一个操作数减少了1/2。因此，对于某些常数c，还原步骤的数量受a的对数约束，基准为sqrt(2)，其为c * log(a)。

• 因式分解：为了检验数字的素数或分解素数的平方，只需检查数字的平方根即可。如果给定的数字具有较小的因子，那么我们需要更少的可分性测试。所以需要的部门数量很容易被sqrt(a)+sqrt(b)限制。由于最多可以有ld(a)因子a和​​其余的比较和乘法得到gcd也受sqrt(a)约束。

Answer 2

要分析欧几里德GCD，你必须选择最差情况下的值：我个人发现斐波那契对最适合这个问题。例如。

EGCD(121393, 75025) = 1; // With 24 iterations (or recursive calls). 

在这个 “序” 请看：

随着斐波那契数对，我们注意到：

121393 % 75025 == 121393 - 75025 == 46368. 

因此，存在121393/46368 = **2.61** (more or less);

减少的因素

当然，最坏的情况下运行时间会使用Small Oh Notation，因为最好的例子是Omega（1），换句话说就是Constant Time，例如，当股利是1000，除数是2时。

既然我们已经减少的因素，我们被允许把像递推关系如下：

你必须要知道，这在运行时间适用完全相同的重复同样的方式EGCD算法的版本。