请问gcd算法求最大公约数的时间复杂度是多少

Question

如题所述

Answer 1

O(x)，执行次数x/2。

如果是用的欧几里得的辗转相除，是O(log n)。

int cm(int a,int b)

{

if (!b) return a;

else return(cm(b,a %b));

}

扩展资料：

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f (n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1),另外，在时间频度不相同时，时间复杂度有可能相同，如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同，但时间复杂度相同，都为O(n2)。

参考资料来源：百度百科-时间复杂性

Answer 2

穷举法O(n)
如果是用的欧几里得的辗转相除，应该是O(log n)本回答被提问者采纳

Answer 3

int gcd(int m,int n){
if(n==0)
return m;
else
return gcd(n,m%n);
}
递归……