0

当我准备介绍算法课中期时，我正在通过教授之前发布的一些测试，我发现了这个问题：

计算 gcd(312,455) 的方法有两种：找到每个数字的因式分解，以及使用欧几里得算法。每种方法的复杂性是多少？

他的回答是：

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)

他是如何理解复杂性的？

4

2 回答 2

1

要分析欧几里得 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 算法的迭代版本完全相同。

于 2014-03-01T20:29:55.040 回答
0

给定的复杂性是所需算术运算数量的粗略最坏情况界限：

  • 欧几里得算法：因为a >= b我们有gcd(a,b) = gcd(b, a mod b)where min(b, a mod b) < a/2，所以在最多两个归约步骤之后，我们至少将第一个操作数归约1/2。因此，减少步骤的数量受a与基础的对数约束，该对数sqrt(2)适用c * log(a)于某个常数c。

  • 因式分解：为了测试数字的素数或分解素数的平方，只需检查直到数字平方根的因数。如果给定数字的因子更小，那么我们需要更少的可分性测试。因此，所需的除法数很容易受 约束sqrt(a)+sqrt(b)。由于最多可以有 的ld(a)因子，a并且ld(a) < sqrt(a)剩余的比较和乘法得到 gcd 也受sqrt(a).

于 2013-02-16T19:39:15.543 回答