锐客网

  1. 首页 > it技术 > >

欧几里得算法(即辗转相除法)的时间复杂度log(N)的简洁证明

algorithm

欧几里得算法描述

/* 求M和N的最大公约数，假设M>=N(如果判断不满足，则直接交换)*/ void gcd(int M,int N){ while(n!=0){ long rem=M%N; M=N; N=rem; } }

时间复杂度证明 证明之前先熟悉这些知识：
1.m mod n的结果在[0,n-1]之间，如果 n > m 2 n>\frac{m}{2} n>2m?,则m mod n的结果就是m -n
2.m mod n < m 2 <\frac{m}{2} <2m?
对2的证明：
? 记 rem为m mod n
? 如果 n ≤ m 2 n\leq\frac{m}{2} n≤2m?,，由1可知， r e m < n rem ? 如果 n > m 2 n>\frac{m}{2} n>2m?,则用1可知， r e m = m ? n < m ? m 2 = m 2 rem=m-n
证明过程
由知识2可知，在两次迭代之后，余数最多为原始值的一般。这就证明了迭代次数至多为 2 l o g ( N ) = O ( l o g N ) 2log(N)=O(logN) 2log(N)=O(logN).
【欧几里得算法(即辗转相除法)的时间复杂度log(N)的简洁证明】理解：观察欧几里得算法的执行过程，第一次迭代后余数至多为 M 2 \frac{M}{2} 2M?,第二次迭代后余数至多为 N 2 \frac{N}{2} 2N?

    推荐阅读


    上一篇：数论/数学|huntian oy（杜教筛 欧拉函数）

    下一篇：JS缓存 按钮点击，下面代码随着切换