c++ - __gcd 的时间复杂度是多少？

Question

__gcd(m,n) 函数的时间复杂度是多少？另外，它是否使用欧几里得方法来计算gcd？

例如代码

#include <iostream> 
#include <algorithm> 

using namespace std; 

int main() { 
    cout << "gcd(10, 25) : " << __gcd(6, 20) << endl; 
} 

标签： c++std

Answer 1

是的，它使用欧几里得方法来计算两个值的 gcd。它的复杂性是 (2) 算法，其中 n 是a和b的上限。

详细信息：https ://www.quora.com/What-is-the-time-complexity-of-Euclids-GCD-algorithm