在前言中提到那本书中也明确指出了欧几里得算法在实现过程理解上可能不是很难，但是想要得出其在平均情况下的性能需要大量的高度复杂的数学运算分析，书中给出了一个最终的迭代平均次数结果：
次数n = (12 * ln2 * lnN) / π ^ 2 + 1.47 (N为其中较小的那个数)
所以后面就只是考虑一个最坏的情况：M、N（M > N）是两个相邻的斐波那契数，程序是这样的（来源于该书）：
long gcd( long m,
求两个正整数的最大公约数欧几里德算法
简单
分析
算法：long gcd( long m, long n ){while( n!=0 ){ long rem = n; n = m % n; m=rem;} return m; }
分析
： 设两个正整数m和n，m >=n != 0，其最大公约数为x。 m = ax; n=b
设 a 和 b 的最大公约数为 c ；
则有 c = gcd( a , b ) ;
设 a = x * c , b = y * c , 其中 x 与 y 互质 （因为 c 是最大公约数）
设 g = a%b = a - i * b = (x - i * y )...
扩展
欧几里得算法
新的改变功能快捷键合理的创建标题，有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants创建一个自定义列表如何创建一个注脚注释也是必不可少的KaTeX数学公式新的甘特图功能，丰富你的文章UML 图表FLowchart流程图导出与导入导出导入
你好！ 这是你第一次使用 Markdown编辑器 所展示的欢迎页。如果你想学习如何使用Markdown编辑器, 可以仔细阅读这篇文章，了解一下Markdow
欧几里得算法
(即辗转相除法)的
时间复杂度
本文是参考新浪博客而写。
欧几里得算法
, 又称辗转相除法, 用于求两个自然数的最大公约数. 算法的思想很
简单
, 基于下面的数论等式
gcd(a, b) = gcd(b, a mod b)
其中gcd(a, b)表示a和b的最大公约数, mod是模运算, 即求a除以b
求最大公约数的最常用的算法是
欧几里得算法
,也称为辗转相除法。问题定义为求i和j的最大公约数gcd(i,j),其中i和j是整数,不妨设i>j。算法可以递归的表示:
1.如果j能整除i,那么gcd(i,j)=j;
2.j不能整除i,令r=i%j,那么gcd(i,j)=gcd(j,r).
上面的算法对于i<j的情况也是可以的，实际上是做了一次交换。
使用C语...
③有穷性：在执行有穷步之后结束，且每一步都在有穷时间内完成
④确定性：算法中的每一条指令必须有确切的含义，对于相同的输入只能得到相同的输出
⑥可行性：算法描述的操作可以通过已经实现的基本操作执行有限次完成
有效算法五...
一、算法的
时间复杂度
定义
在进行算法
分析
时，语句总的执行
次数
T(n)是关于问题规模n的函数，进而
分析
T(n)随n的变化情况并确定T(n)的数量级。算法的
时间复杂度
，也就是算法的时间量度。记作：T(n)=O(f(n))。它表示随问题n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进
时间复杂度
，简称为
时间复杂度
。其中，f(n)是问题规模n的某个函数。
这样用大写O()来体现算法时
