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

Question

如果使用欧几里得扩展算法计算两个n位值x和y的最大公约数，那么涉及的比特复杂度是多少，即以n为复杂度的衡量标准。

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

以两个值x和y的大小作为复杂度的衡量标准，其复杂度接近于：

来源

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

- Tabish Mir

---

引用的公式似乎不正确。例如，可以在这里查看：https://math.stackexchange.com/questions/258596/what-is-the-time-complexity-of-euclids-algorithm-upper-bound-lower-bound-and-a 此外，“扩展”对于渐近复杂度来说是无关紧要的。它只贡献了一个常数因子。 - Henry

Answer 1

我希望你正在寻找最坏情况的复杂度，因为你正在关注顶峰。

无论如何...

如果a和b有N位长，则在最坏情况下（斐波那契对），扩展欧几里得算法将需要O(N)次迭代。

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

现在，f(N)的确切值取决于您的库中实现大整数操作的细节。除法/余数运算将占主导地位，尽管维基百科称，如果您使用牛顿-拉夫逊法则，则其复杂度与乘法相同（尽管肯定会有一个常数乘数！）。

在极限情况下，使用Schönhage-Strassen算法，乘法成本为O(N * log N * log log N)，希望您的库最终也会使用它...因此当数字变得非常大时，扩展欧几里得算法的最坏情况下将需要O(N² * log N * log log N)。

- Matt Timmermans