首页 > 试题广场 >

以下程序是用来计算两个非负数之间的最大公约数： long

[单选题]
以下程序是用来计算两个非负数之间的最大公约数： 
long long gcd(long long x, long long y) { 
    if (y == 0) 
        return x; 
    else 
        return gcd(y, x % y); 
}
我们假设x,y中最大的那个数的长度为n，基本运算时间复杂度为O(1)，那么该程序的时间复杂度为()： 
  • O(1)
  • O(logn)
  • O(n)
  • O(n^2)
查看正确选项
添加回答
阳光下的米雪头像 阳光下的米雪
发表于 2019-05-02 09:52:38 回复(4)
Zack头像 Zack
求最大公约数用的是辗转相除法（欧几里得算法），所以是O(logn)[5]。
发表于 2014-10-25 00:26:14 回复(0)
困～～～头像 困～～～
对于gcd(a,b),假设a,b中最大的数为a,则若调用了k次，则a>=F(k+2),b>=F(k+1),F(x)为第x个斐波拉切数，而F(x)=m^x/sqrt(5),因此这题最坏时间复杂度应该为O(n)，与这个数的长度成正比
发表于 2015-06-28 11:35:21 回复(5)
冲鸭！冲鸭！冲鸭！头像 冲鸭！冲鸭！冲鸭！
long long gcd(long long x, long long y) { # x是被除数， y是除数
    if(y == 0)
        returnx;
    else
        return gcd(y, x % y);
}
使用辗转相除法（欧几里得算法）求两个非负整数的最大公约数：20,12
20 ÷ 12 = 1 ... 8
---------------------
12 ÷ 8 = 1 ... 4
8 ÷ 4 = 2 .... 0
所以20和12的最大公约数是4。需要迭代2次，基本运算次数为3。





发表于 2019-08-01 12:24:24 回复(0)
loveCoding头像 loveCoding
同样的提答案不一样，管理员能告我一下我这是为什么嘛？麻烦认真核对一下:)
发表于 2015-04-01 21:46:36 回复(1)
牛客733423号头像 牛客733423号
o(logn) 因为最小质因子就是2了 用最简单的寻找相同质因子的方法 两个数分别是2的m , n 次方
当m == n 时 为logn
发表于 2015-05-06 23:18:32 回复(0)
mlc头像 mlc
和第三题相同，怎么答案不同
发表于 2015-04-01 12:06:57 回复(0)
东河西岸头像 东河西岸
辗转相除法时间复杂度为logn
发表于 2020-08-10 08:54:23 回复(0)
uchiyou头像 uchiyou
（用空间换取时间）
最大公约数用的是辗转相除法（欧几里得算法）
发表于 2016-03-21 11:33:53 回复(0)
ChatGPT3头像 ChatGPT3

每次迭代都可以将两个数中较大的数变成原来的一半左右，因此最多迭代 次就可以求出最大公约数。每次迭代的时间复杂度是 ，因此总的时间复杂度是 。

发表于 2023-04-22 07:59:04 回复(0)
AAS48头像 AAS48
辗转相除法 O(logn)
发表于 2021-12-14 19:16:51 回复(0)
ILSYT头像 ILSYT

是常识...可是这题说“长度”那不就了嘛，，，

发表于 2019-10-15 22:54:16 回复(0)
你好明天fengge头像 你好明天fengge
递归

发表于 2018-01-30 19:52:15 回复(0)
七宝Wendy头像 七宝Wendy
求最大公约数用的是辗转相除法（欧几里得算法），所以是O(logn)
发表于 2017-08-12 21:09:44 回复(1)
林夕9头像 林夕9
b.
发表于 2016-07-31 09:18:47 回复(0)
牛客611309号头像 牛客611309号
答案不是n吧
发表于 2015-09-10 19:04:27 回复(0)
月夜星空头像 月夜星空
咋觉得是常数时间？？？
发表于 2015-09-05 23:24:34 回复(0)
ufo008ahw头像 ufo008ahw
长度是什么鬼，醉了
发表于 2015-07-27 01:07:15 回复(0)
江山如画君头像 江山如画君
为什么同样的题目在不同的卷子里面答案还不一样......
发表于 2015-03-31 09:11:50 回复(2)
小海豹头像 小海豹
O(n)
发表于 2014-11-01 11:13:30 回复(2)
提交观点

问题信息

谷歌 复杂度 递归
来自：Google2013笔试卷
难度：
21条回答 16861浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号