首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 软件管理 > 软件架构设计 >

求大神讲一下子时间复杂度

2013-03-29 
求大神讲一下时间复杂度为什么欧几里得算法的时间复杂度是O(logn)?1.10 一下程序是用来计算两个非负数之间

求大神讲一下时间复杂度
为什么欧几里得算法的时间复杂度是O(logn)?

1.10 一下程序是用来计算两个非负数之间的最大公约数:


long long gcd(long long x, long long y) {


if( y==0) return 0;


else return gcd (y, x%y);


}我们假设x,y中最大的那个数的长度为n,基本运算时间复杂度为O(1),那么该程序的时间复杂度为:


A.O(1)B.O(logn)C.O(n)D.O(n^2)
[解决办法]
>为什么欧几里得算法的时间复杂度是O(logn)?
连续做两次以后最大数肯定能至少减半,然后取Fibonacci数列相邻两项能压到最坏复杂度。

热点排行