扩展欧几里德算法的位复杂度是多少？

Question

使用欧几里得扩展算法计算两个 n 位值 x 和 y 的最大公约数时涉及的位复杂度是多少，即 n 的复杂度

在不同位大小的最坏情况下，我在使用标准扩展欧几里德算法计算 GCD 时观察到以下模式。

就 x 和 y 两个值的大小而言，复杂度接近于该值：

来源

如何得出理论位复杂度来验证我的观察结果？

Answer 1

我希望你能适应高峰，因为你正在寻找最坏情况的复杂性。

反正...

如果a和b 的长度为N位，那么在最坏的情况下（斐波那契对），扩展欧几里得算法将进行O(N)次迭代。

令f(N)为单次迭代的成本。当然f(N)至少是线性的，但仍然是多项式，并且在每种情况下近一半的迭代将涉及至少N/2位长的参数，因此总复杂度将是O(N * f(N) )

现在，f(N)究竟是什么将取决于您的库中如何实现大整数运算的细节。除法/余数运算将占主导地位，尽管维基百科说如果你使用牛顿-拉夫森除法，那么它的复杂性与乘法相同（尽管肯定会有一个常数乘数！）。

乘法花费O（N *登录N * log日志N）与Schönhage-施特拉森的限制，并希望您的图书馆将使用最终...所以如果这些数字确实很大，扩展欧几里德算法应该采取O（N ² * log N * log log N)在最坏的情况下。