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

Question

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

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

x 和 y 两个值的大小的复杂度接近于值:

Source

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

Answer 1

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

无论如何...

如果a 和b 是N 位长，那么在最坏的情况下(斐波那契对)，扩展欧几里德算法将采用< strong>O(N) 次迭代。

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

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

乘法成本 O(N * log N * log log N) 在 Schönhage–Strassen 的限制下，希望你的图书馆最终会使用它......所以当数字得到 真的很大，扩展欧几里德算法在最坏的情况下应该采用O(N² * log N * log log N)。