以下gcd算法的时间复杂度 [英] time complexity of below gcd algorithm

问题描述

我发现很难计算二进制GCD算法的时间复杂度，该算法也称为Stein算法，给出为O（n ^ 2），其中n是这两个数字。
不应该是O（n）吗？
算法如下：

I have been finding it difficult to calculate the time complexity of The binary GCD algorithm, also known as Stein's algorithm which is given to be O(n^2) where n is the number of bits in the larger of the two numbers. Shouldn't it be O(n) ? Algorithm is as below :

1.gcd（0，v） = v，因为一切都除零，并且v是除v的最大数。类似地，gcd（u，0）= u。通常没有定义gcd（0，0），但是将gcd（0，0）设置为0很方便。

1.gcd(0, v) = v, because everything divides zero, and v is the largest number that divides v. Similarly, gcd(u, 0) = u. gcd(0, 0) is not typically defined, but it is convenient to set gcd(0, 0) = 0.

2。如果u和v均为偶数，则gcd（u，v）= 2·gcd（u / 2，v / 2），因为2是一个公约数。

2.If u and v are both even, then gcd(u, v) = 2·gcd(u/2, v/2), because 2 is a common divisor.

3。如果u为偶数并且v是奇数，则gcd（u，v）= gcd（u / 2，v），因为2不是一个常见的除数。同样，如果u为奇数，v为偶数，则gcd（u，v）= gcd（u，v / 2）。

3.If u is even and v is odd, then gcd(u, v) = gcd(u/2, v), because 2 is not a common divisor. Similarly, if u is odd and v is even, then gcd(u, v) = gcd(u, v/2).

4。如果u和v为都为奇数且u≥v，则gcd（u，v）= gcd（（u − v）/ 2，v）。如果两个都是奇数，且u ＜ v，然后gcd（u，v）= gcd（（v − u）/ 2，u）。这些是简单欧几里德算法的一个步骤（在每个步骤中都使用减法）以及上述步骤3的应用的组合。除以2得出整数，因为两个奇数之差为偶数。[3]

4.If u and v are both odd, and u ≥ v, then gcd(u, v) = gcd((u − v)/2, v). If both are odd and u < v, then gcd(u, v) = gcd((v − u)/2, u). These are combinations of one step of the simple Euclidean algorithm, which uses subtraction at each step, and an application of step 3 above. The division by 2 results in an integer because the difference of two odd numbers is even.[3]

5。重复步骤2-4，直到u = v或（再执行一个步骤）直到u =0。无论哪种情况，GCD都是2kv，其中k是在步骤2中找到的2的公因子数。

5.Repeat steps 2–4 until u = v, or (one more step) until u = 0. In either case, the GCD is 2kv, where k is the number of common factors of 2 found in step 2.

推荐答案

Knuth第2卷有一个非常复杂的分析，似乎证实了显而易见的猜测，即步数在输入比特数中是最坏的情况。但是，对于非常大的n，每个减法都必须单独以O（n）收费（例如，由于多重精度算法），在这种情况下，总费用为O（n ^ 2）

Knuth volume 2 has a very sophisticated analysis which seems to confirm the obvious guess that the number of steps is worst case linear in the number of input bits. However for very large n each subtraction needs to be charged as O(n) in its own right (for example due to multiple precision arithmetic) in which case the total bill is O(n^2)

这篇关于以下gcd算法的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！