当前位置:首页 > 高性能开发 > 数据结构与算法

欧几里得算法:从证实等式gcd(m, n) = gcd(n, m mod n)对每一对正整数m, n都成立说开去

优良自学吧提供欧几里得算法:从证实等式gcd(m, n) = gcd(n, m mod n)对每一对正整数m, n都成立说开去,欧几里得算法:从证明等式gcd(m, n) = gcd(n, m mod n)对每一对正整数m, n都成立说开去写诗或者写程序的时候,我们经常要跟欧几里得算法打交道。然而有没要考虑到为什么欧几里得算法是有效且高效的,一些偏激(好吧,请允许我用这个带有浓重个人情感色彩的

欧几里得算法:从证明等式gcd(m, n) = gcd(n, m mod n)对每一对正整数m, n都成立说开去

写诗或者写程序的时候,我们经常要跟欧几里得算法打交道。然而有没要考虑到为什么欧几里得算法是有效且高效的,一些偏激(好吧,请允许我用这个带有浓重个人情感色彩的词汇)的计算机科学家认为,除非程序的正确性在数学上得到了完全严格的证实,否则我们不能认为程序是正确的。既然存在即合理,因此下面我就详细得解说一下欧几里得算法,它为什么是正确的算法(算法过程就不给出了,有了思想,无论是迭代还是循环实现应该都不成问题),为什么有那么好的时间复杂性。

首先还是证明上述命题:注意到证明了该命题就证明了欧几里得算法的正确性。

证明:令d = gcd(m, n),则d|m 且d|n。设m = kn + r(0≤ r < n),则 d|(kn+r)。又有d|n,因此d|kn,所以有d|r。即我们由d|m 且d|n 这个前提可以得出d|r。换就话说,我们也可以说成由d|m 且d|n 这个前提推出了d|n 且 d|r。使用类似的推理过程同样可以得到:由d|n 且 d|r 可以推出d|m 且 d|n。注意到这里的r 即 m mod n。因此我们可以说gcd(m, n) = gcd(n, m mod n)是双向成立的,命题得证。

关于欧几里得定理我还是想多说一点,那就是欧几里得本人给出的证明过程,他的思维清晰,逻辑严密,虽然采用的几何证法,但是不失严密和优美。下面我就简略地复述一遍我们敬爱的欧几里得先生给出的证明,原版证明见欧几里得的成名作品《几何原本》:如果m 和n 互素,那么它们的最大公约数显然是1。如果两者不互素的话:首先,想象两段线段,它们的长度分别是m 和n。姑且把他们称作线段AB 和CD。我们取其中较短的一段量取另一段,姑且认为CD 是其中较短的线段,如果CD 量尽AB,这时它也量尽它自己,那么CD 就是CD、AB的一个公度数,显然CD 同时也是最大公度数,因为没有比CD 大的数能量尽CD。但是,如果CD 量不尽AB,那么从AB,CD中的较大者中不断地减去较小者,如此,将有一个余数能量尽它前面一个。我们说这个数就是m 和n 的最大公度数,为什么呢?假设这个余数不是最大公度数,那么必有大于该数的一个数能量尽AB 和 CD,最后我们能推出大于该余数的这个数能量尽这个余数,注意到这是不可能的,因为较大的数量尽较小的数是不可能的。通过这个反证的过程,我们知道没有大于该余数的数能量尽AB,CD。因而这个数就是AB 和 CD也即m 和n 的最大公度数。

好了,证明到这里先告一段落,下面我们来考察一下欧几里得算法的效率。

令r0 = m mod n, r1 = n mod r0。于是有gcd(m, n) = gcd(n, r0) = gcd(r0, r1)。只需要注意到这一事实:r0 < m/2 或者 r1 < n/2。就可以知道在两步之内算法的规模减半了,也就是说,其时间复杂度为2logn = O(logn)。这就是其时间复杂度的上界。如果你随便写一个算法,它的时间复杂度是O(logn),那么世界该有多么美好啊。

 


(本文来自互联网,不代表搜站(http://www.ylzx8.cn/)的观点和立场)
本站所有内容来自互联网,若本站收录的信息无意侵犯了贵司版权,请给我们来信(ylzx8cn@163.com),我们会及时处理和回复,谢谢