我希望你正在寻找最坏情况的复杂度,因为你正在关注顶峰。
无论如何...
如果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(N2 * log N * log log N)。