欧氏算法的时间复杂度

我很难确定欧几里得最大公分母算法的时间复杂度是多少。这个伪代码算法是:

function gcd(a, b)
while b ≠ 0
t := b
b := a mod b
a := t
return a

它似乎取决于 一和 b。我认为时间复杂度是 O (a% b)。是这样吗？还有更好的写法吗？

121614 次浏览
小开

在 维基百科文章上看得很清楚。

对于值对，它甚至有一个很好的复杂性图。

不是 O(a%b)。

众所周知(见文章) ，它将永远不会采取超过五倍的数字在较小的数字步骤。因此，最大步数随着 (ln b)位数的增加而增加。每个步骤的成本也随着位数的增加而增加，因此复杂度受到 O(ln^2 b)的限制，其中 b 是较小的位数。这是一个上限，实际时间通常更短。

小开

参见 给你。

特别是这一部分:

拉梅指出，当两个数小于 n 时，到达最大公约数所需的步数是

alt text

所以 O(log min(a, b))是一个很好的上界。

小开

欧几里得算法的最坏情况是当余数在每一步都是最大的时候，也就是说。对于斐波那契数列的两个连续项。

当 n 和 m 是 a 和 b 的位数时，假设 n > = m，算法使用 O (m)除法。

注意，复杂度总是根据输入的 尺寸给出的，在这种情况下是数字的个数。

小开
最佳答案

分析欧几里得算法的时间复杂性的一个技巧是，跟踪两次迭代中发生的情况:

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%
  • Tiny B: a % b < b and 2b <= a, so a is decreased by at least half, so a+b decreased by at least 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乘以一个多对数因子。差不多 n^2 lg(n) 2^O(log* n).通过使用 二进制 GCD可以避免多对数因子。

小开

分析算法的合适方法是确定算法的最坏情况。 当涉及到斐波那契对时，欧几里得 GCD 的最坏情况发生。 void EGCD(fib[i], fib[i - 1])，在这里我 > 0。

例如，让我们选择红利为55，除数为34的情况(回想一下我们仍然在处理斐波那契数)。

enter image description here

正如您可能注意到的，这个操作花费了8次迭代(或递归调用)。

让我们试试更大的斐波那契数，即121393和75025。我们还可以注意到，它进行了24次迭代(或递归调用)。

enter image description here

您还可以注意到，每次迭代都会产生一个斐波那契数列。所以我们才有这么多行动。我们不能只用斐波那契数得到类似的结果。

因此，这次时间复杂度将用小 Oh (上界)表示。下界直观地是欧米茄(1) : 例如，500除以2的情况。

让我们来解决这个递回关系式:

enter image description here

我们可以说，欧几里得 GCD 可以使 log (xy)运算 最多。

小开

然而，对于迭代算法，我们有:

int iterativeEGCD(long long n, long long m) {
long long a;
int numberOfIterations = 0;
while ( n != 0 ) {
a = m;
m = n;
n = a % n;
numberOfIterations ++;
}
printf("\nIterative GCD iterated %d times.", numberOfIterations);
return m;
}

对于斐波那契数对，iterativeEGCD()和 iterativeEGCDForWorstCase()没有区别，后者看起来如下:

int iterativeEGCDForWorstCase(long long n, long long m) {
long long a;
int numberOfIterations = 0;
while ( n != 0 ) {
a = m;
m = n;
n = a - n;
numberOfIterations ++;
}
printf("\nIterative GCD iterated %d times.", numberOfIterations);
return m;
}

是的，与斐波那契对，n = a % n和 n = a - n，这是完全相同的事情。

We also know that, in an earlier response for the same question, there is a prevailing decreasing factor: factor = m / (n % m).

因此，为了将欧几里得 GCD 的迭代版本塑造成一个确定的形式，我们可以把它描述成这样一个“模拟器”:

void iterativeGCDSimulator(long long x, long long y) {
long long i;
double factor = x / (double)(x % y);
int numberOfIterations = 0;
for ( i = x * y ; i >= 1 ; i = i / factor) {
numberOfIterations ++;
}
printf("\nIterative GCD Simulator iterated %d times.", numberOfIterations);
}

根据 Jauhar Ali 博士的 工作(最后一张幻灯片) ，上面的循环是对数的。

enter image description here

是的，小欧，因为模拟器告诉的迭代次数 最多。非斐波那契对在欧几里得 GCD 上的迭代次数要比斐波那契对少。

小开

以下是对欧几里得算法运行时复杂性的直观理解。正式的证明包含在各种文本中，如算法简介和 TAOCP 第2卷。

首先想想如果我们取两个斐波那契数 F (k + 1)和 F (k)的 gcd。你可能会很快发现，欧几里得的算法迭代到 F (k)和 F (k-1)。也就是说，在每次迭代中，我们向下移动斐波那契数列中的一个数。由于 Fibonacci 数是 O (Phi ^ k) ，其中 Phi 是黄金比率，我们可以看到 GCD 的运行时间是 O (log n) ，其中 n = max (a，b) ，log 以 Phi 为基数。接下来，我们可以证明这将是最坏的情况，通过观察斐波那契数一直产生对，其余部分在每次迭代中保持足够大，并且直到你到达序列的开始才变为零。

我们可以使 O (logn) ，其中 n = max (a，b)的束缚更加紧密。假设 b > = a，这样我们就可以在 O (log b)上写定界。首先，观察 GCD (ka，kb) = GCD (a，b)。由于 k 的最大值是 gcd (a，c) ，因此我们可以在运行时用 b/gcd (a，b)替换 b，从而得到更紧的 O 界(log b/gcd (a，b))。

小开

Gabriel Lame 的定理通过 log (1/sqrt (5) * (a + 1/2))-2限制步数，其中 log 的基数是(1 + sqrt (5))/2。这是算法的最坏情况，当输入是连续的 Fibanoci 数时发生。

稍微自由一点的界限是: log a，其中 log 的底部是(sqrt (2)) ，Koblitz 暗示了这一点。

出于密码学的目的，我们通常考虑算法的逐位复杂度，考虑到位大小近似由 k = loga 给出。

Here is a detailed analysis of the bitwise complexity of Euclid Algorith:

Although in most references the bitwise complexity of Euclid Algorithm is given by O(loga)^3 there exists a tighter bound which is O(loga)^2.

考虑: r0 = a，r1 = b，r0 = q1.r1 + r2... ... ，ri-1 = qi.ri + ri + 1，... ... ，rm-2 = qm-1. rm-1 + rm rm-1 = qm.rm

观察到: a = r0 > = b = r1 > r2 > r3... > rm-1 > rm > 0... ...

and rm is the greatest common divisor of a and b.

在 Koblitz 的一本书(数论和密码学课程)中，可以证明:

同样，在 Koblitz，将一个 k 位正整数除以一个 l 位正整数(假设 k > = l)所需的位操作数是: (k-l + 1)。我... ...

(1)和(2)除法的次数是 O (loga) ，因此(3)的总复杂度是 O (loga) ^ 3。

现在在 Koblitz 的一句话可以把这个数字减少到0(loga) ^ 2。

考虑 ki = logri + 1

通过(1)和(2) ，我们得到: i = 0,1，... ，m-2，m-1和 ki + 2 < = (ki)-1，i = 0,1，... ，m-2

(3)对于 i = 0,1,2，. . m，m 除法的总成本以 SUM [(ki-1)-((ki)-1))] * ki 为界

重新排列: SUM [(ki-1)-((ki)-1)] * ki < = 4 * k0 ^ 2

所以欧几里得算法的复杂度是 o (loga) ^ 2。

小开

当 n 和 m 都是连续的斐波那契数时，会出现最坏的情况。

Gcd (Fn，Fn-1) = gcd (Fn-1，Fn-2) = ⋯⋯ = gcd (F1，F0) = 1，nth 斐波那契数列为1.618 ^ n，其中1.618是黄金比率。

所以，要找到 gcd (n，m) ，递归调用的次数 Θ (logn)。

小开

下面是 Mark Allen Weiss的《 C 中的数据结构和算法分析》一书(第二版，2.4.4)中的分析:

欧几里得算法的工作原理是不断地计算余数直到0为止，最后一个非零余数就是答案。

密码如下:

unsigned int Gcd(unsigned int M, unsigned int N)
{


unsigned int Rem;
while (N > 0) {
Rem = M % N;
M = N;
N = Rem;
}
Return M;
}

Here is a 定理 that we are going to use:

如果 M > N，那么 M mod N < M/2。

证据:

有两种情况，如果 N < = M/2，那么由于余数较小 比 N 大，这个定理对这个情况成立，另一个情况是 N > M/2。 But then N goes into M once with a remainder M - N < M/2, proving the 定理。

因此，我们可以做出以下推论:

Variables    M      N      Rem


initial      M      N      M%N


1 iteration  N     M%N    N%(M%N)


2 iterations M%N  N%(M%N) (M%N)%(N%(M%N)) < (M%N)/2

因此，在两次迭代之后，余数最多只有原始值的一半。这将显示迭代次数最多为 2logN = O(logN)。

注意，算法计算 Gcd (M，N) ，假设 M > = N (如果 N > M，循环的第一次迭代将它们交换)

小开

每一步都有两个案例

B > = a/2，那么 a，b = b，a% b 最多只能得到 b 之前值的一半

B < a/2，那么 a，b = b，a% b 最多只能得到先前值的一半，因为 b 小于 a/2

因此，在每一步，算法将减少至少一个数字至少一半。

在最多 O (log a) + O (log b)步骤中，这将减少到简单的情况。它产生一个 O (logn)算法，其中 n 是 a 和 b 的上限。

我找到了


提交答案