精华内容
下载资源
问答
  • 斐波那契数列 注:此时 ...欧几里得算法复杂度: 我们不妨设A>B>=1(若a<b我们只需多做一次模运算, 若B=0或A=B模运算的次数分别为0和1) 构造数列{Un}:  U0=a, U1=b, Uk=Uk-2mod Uk-1(k&...

    斐波那契数列

      

    :此时  

    指数增长

      F(0)=0,F(1)=1, F(n)=F(n-1)+F(n-2)(n>=2,n∈N*)

    欧几里得算法复杂度:

    我们不妨设A>B>=1(若a<b我们只需多做一次模运算, 若B=0或A=B模运算的次数分别为0和1)

    构造数列{Un}:

      U0=a, U1=b, Uk=Uk-2 mod Uk-1 (k>=2)

    若算法需要n次模运算, 则有

      Un=gcd(a, b), Un+1=0

    我们比较数列{Un}和菲波那契数列{Fn}

      F0=0,F1=1<=Un ,F2=1<=Un-1

    又因为由  

      Uk mod Uk+1=Uk+2

    可得    

      Uk>=Uk+1+Uk+2     (Uk=r·Uk+1+Uk+2,r>=1) 

    由数学归纳法得到 :   

      Uk>=Fn-k+1

    于是得到:

      A=U0>=Fn+1

      B=U1>=Fn

    也就是说如果欧几里得算法需要做n次模运算, 则B必定不小于Fn.

    换句话说, 若 B<Fn, 则算法所需模运算的次数必定小于n.

    根据菲波那契数列的性质, 有

      Fn>1.618n/√5 

      b>1.618n/√5

    所以模运算的次数为 O( lg B ).

     

    转载于:https://www.cnblogs.com/Bird-Xu/p/8180036.html

    展开全文
  • 辗转相除法的时间复杂度

    万次阅读 2017-03-27 20:48:31
    以下程序是用辗转相除法来计算两个非负数之间的最大公约数: long long gcd(long long x, long long y) {  if (y == 0)  return x;  else  return gcd(y, x % y); }  我们假设x,y中最大的那个数的长度为n...

    以下程序是用辗转相除法来计算两个非负数之间的最大公约数:

    long long gcd(long long x, long long y) {
        if (y == 0)
            return x;
        else
            return gcd(y, x % y);
    }


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

    求最大公约数的最常用的算法是欧几里得算法,也称为辗转相除法.
    问题定义为求ij的最大公约数gcd(i,j),其中ij是整数,不妨设i>j.
    算法可以递归的表示:
    1.如果j能整除i,那么gcd(i,j)=j;
    2.j不能整除i,r=i%j,那么gcd(i,j)=gcd(j,r).
    使用C语言实现:

    int gcd(int i, int j)
    {
        int r = i % j;
        return r == 0 ? j : gcd(j, r);
    }


    关键是要证明步骤 2. 正确性分析:
    算法的步骤1,显然成立(最大公约数定义).

    dij的最大公约数,
    那么i=md,j=nd,mn互质(否则d不是最大公约数).
    r=i%j可以得到i=kj+r,k=⌊m/n⌋,k≥1(我们前面假设过i>j).
    i=md,j=nd代入得到
    md=knd+r
    那么
    r=(m-kn)d
    m-knm也是互质的.
    所以得到djr的最大公约数.

    时间复杂度分析:
    逆着看该算法,最后的余数是0,倒数第二次余数是d,倒数第三次是kd,k>1…
    由于组成了一个数列,{0,d,kd,nkd+d,…}
    数列的n项加上n+1,n+2项要小,所以比斐波纳契数列增长的要快.
    我们已知斐波纳契数列增长速度是指数,那么待分析的数列也是指数增长.
    设欧几里得算法需要k,那么j=O(2^k),k=O(lg j).

    所以欧几里得算法求最大公约数的时间复杂度是对数量级的,速度非常快.

    zz from http://guozi149.me/tech/foundations/math/212

     

    展开全文
  • 首先看下辗转相除法的递归及非递归代码实现: //递归实现 int gcd(int a,int b) { return b?gcd(b,a%b):a; } //非递归实现 int gcd(int a,int b) { int t; while(b) { t = a; a = b; b = t%b; } ...

    首先看下辗转相除法的递归及非递归代码实现:

    <span style="font-size:18px;">//递归实现
    int gcd(int a,int b) {
    	return b?gcd(b,a%b):a;
    } </span>

    <span style="font-size:18px;">//非递归实现
    int gcd(int a,int b)
    {
    	int t;
    	while(b)
    	{
    		t = a;
    		a = b;
    		b = t%b;
    	}
    	return a;
    }</span>

    代码实现不难,不过怎么证明呢?

    其实从递归代码不难看出只要证明gcd(a,b) = gcd(b,a%b)取余即可。

    我们知道有这样一个等式:a = b*q+r,那么r = a-b*q = d(m-n*q),所以显然a,b的最大公约数d也是r的因数,所以b,r 必有一个约数d,那么为什么d一定是b,r的最大公约数呢?

    回过头来看a = b*q+r,我们可以采用反证法,假设存在D>d为b,r的公约数,那么显然a,b的最大公约数就变为D了,与a,b的最大公约数为d矛盾,所以b,r的最大公约数也为d.这样正如上面所示通过递归就很容易实现相应算法了。


    下面我们再来看下辗转相除法的时间复杂度。

    网上查了下时间复杂度为log2(n),不过证明好像挺麻烦的,对于我这种数学渣渣,,,更是如此。。。

    下面证明转载自:http://blog.sina.com.cn/s/blog_647d97b10100lf7k.html

    注:如有侵权联系我删除

    我们先不考虑模运算本身的时间复杂度(算术运算的时间复杂度在Knuth的TAOCP中有详细的讨论), 我们只考虑这样的问题: 欧几里得算法在最坏情况下所需的模运算次数和输入的a和b的大小有怎样的关系?
    我们不妨设a>b>=1(若a<b我们只需多做一次模运算, 若b=0或a=b模运算的次数分别为0和1), 构造数列{u n}: u 0=a, u 1=b, u k=u k-2 mod u k-1(k>=2), 显然, 若算法需要n次模运算, 则有u n=gcd(a, b), u n+1=0. 我们比较数列{u n}和菲波那契数列{F n}, F 0=1<=u n, F 1=1<=u n-1, 又因为由u k mod u k+1=u k+2, 可得u k>=u k+1+u k+2, 由数学归纳法容易得到u k>=F n-k, 于是得到a=u 0>=F n, b=u 0>=F n-1. 也就是说如果欧几里得算法需要做n次模运算, 则b必定不小于F n-1. 换句话说, 若  b<F n-1, 则算法所需模运算的次数必定小于n. 根据菲波那契数列的性质, 有F n-1>(1.618) n/sqrt(5), 即b>(1.618) n/sqrt(5), 所以模运算的次数为O(lgb).

    如果有大神有更容易理解的证明,欢迎提出交流。


    展开全文
  • 辗转相除法证明及复杂度计算

    千次阅读 2016-08-30 17:45:54
    辗转相除法是计算两个数最大公约数(Greatest conmmon divisor)的一种对数复杂度算法。 问题:有两个正整数 x , y ,求 gcd(x,y): 算法证明: 设 x > y , 且 x = r + y * c , 其中 r >= 0, c >= 0 ; 1. if r = 0...

    辗转相除法是计算两个数最大公约数(Greatest conmmon divisor)的一种对数复杂度算法。

    问题:有两个正整数 x , y ,求 gcd(x,y):

    算法证明:

    设 x > y ,  且 x = r + y * c , 其中 r  >= 0, c >= 0 ;    

    1. if r = 0  then gcd( x,y) == y 为结束条件)

    2. if c = 0  then 算法没有前进

    3. if r > 0 && c >0 then r = x - c * y , 

    易知 : 如果d 为 x, y的公约数, 则必为r = x - c*y 的公约数 ,即 x,y 的公约数必为 y, r 的公约数;

    如果e 为 r和y的公约数, 有 r / e = x / e - c * y / e, r / e , c*y/e 为正整数, x / e 也为正整数,即y, r的公约数必为x,y的公约数;

    综上,x,y的最大公约数等价于y, r的最大公约数由此易得递归算法:

    int gcd ( int x, int y )
    {
    	if( x < y )
    		swap( x, y );
    	int r =  x % y;
    	if( r == 0 )
    		return y;
    	else
    		return gcd( y , r  );
    }
    int main()
    {
    	cout<< gcd( 9, 15 );
    }

    算法复杂度:设 x > y ,  且 x = r + y * c , 其中 r = x % y , c > 0 ;

            得:x > r *( c+1 ) >  2 * r ;   

            即: 经过两次迭代, x至少缩小一倍,算法复杂度为 2*log2(N);



    展开全文
  • 欧几里得算法(即辗转相除法)的时间复杂度

    万次阅读 多人点赞 2015-03-28 16:56:34
    欧几里得算法(即辗转相除法)的时间复杂度 本文是参考新浪博客而写。 欧几里得算法, 又称辗转相除法, 用于求两个自然数的最大公约数. 算法的思想很简单, 基于下面的数论等式 gcd(a, b) = gcd(b, a mod b) 其中...
  • 计算gcd(a,b) 不妨假设a&gt;b,这样 所以每一次余数部分都要小于输入的一半,这样轮番操作a,b 最终的时间复杂度是O(log n)的
  • 欧几里得算法核心: gcd( a , b ) = gcd( b , a%b ) ,其中 gcd 表示 a 和 b 的最大公约数; 证明: ...设 a 和 b 的最大公约数为 c ...综上,最坏时间复杂度 约为 O(2logN) ,去掉常数即为 O(logN) , 底数为 2;
  • 本文对欧几里得算法运行时间复杂度进行了简洁证明。证明过程仅仅利用了余数的定义。结论是该算法的时间复杂度为O(logN)。
  • 辗转相除

    2020-12-16 23:14:13
    辗转相除法来求最大公约数,借机分析一下尾递归与普通递归的区别,未完待续 //辗转相除法 int gcd(int a,int b){ //尾递归 if(b == 0) return a; return gcd(b,a % b); } int gcd2(int a,int b){ if(b == 0...
  • 图解辗转相除

    千次阅读 2019-11-25 23:25:32
    虽然在很久很久以前刚入门ACM的时候就已经知道辗转相除法的存在,并且也用GCD解了不少题,不过说实话辗转相除法的原理一直不是很清楚。 直到最近做到这样一道题: Codeforces - 343A,本以为是一道憨批构造,结果构造...
  • 辗转相除法的算法

    2020-12-10 18:04:16
    展开全部自然语言描述用辗转相除法确定两个正整数e69da5e6ba903231313335323631343130323136353331333339666665 a 和 b(a≥b) 的最大公因数gcd(a,b):当a mod b=0 时gcd(a,b)=b,否则gcd(a,b) = gcd(b,a mod b)递归或...
  • 辗转相除法和更相减损术

    千次阅读 2019-09-03 15:41:19
    高中学过的求大公约数的方法就是辗转相除法和更相减损术了。 辗转相除法递归版 #include <iostream> using std::cin; using std::cout; using std::endl; int gcd(int a, int b) { return b == 0 ? a : gcd(b...
  • 高斯消元辗转相除法的复杂度分析 高斯消元在模意义下时有一种流传甚广的写法——辗转相除法,复杂度也是 O(n3)O(n^3)O(n3) ,但是码量小,十分好写。 具体操作是枚举第 iii 个未知数,将除第 iii 个方程以外的其他...
  • c++ 辗转相除法 递归非递归

    千次阅读 2016-03-26 18:22:52
    #include #include #include using namespace std;...//求最大公约数 辗转相除法 long long gcd(long long x,long long y){ if(x>y)return gcd(y,x); if(x==0)return y; return gcd(y%x,x); } long
  • 下载地址:http://pan.baidu.com/s/1jIt6UlK 转载于:https://www.cnblogs.com/cmyg/p/6604667.html
  • int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
  • http://blog.csdn.net/jtujtujtu/article/details/44071712009辗转相除法求最大公约数:辗转相除法, 又名欧几里德算法(Euclidean algorithm)乃求两个正整数之最大公因子的算法。它是已知最古老的算法, 其可追溯至前...
  • 后附完整源代码:(含有求最大公倍数的函数,此代码测试的是...1. 辗转相除法:此种方法核心如其名,辗转,大数放a中,小数放b中。大的除以小的,余数为零,则小数为最大公约数,不为零则,将余数与b比较大的放a,...
  • 浅谈辗转相除

    2021-04-26 10:38:43
    本文主要包含辗转相除法的正确性证明,以及时间复杂度证明。已经懂了的老铁可以右滑退出了(或者拉倒最下面点亮小手)~ 如何求最大公约数 给定两个正整数,求解最大公约数,代码很简单,比如直接使用__gcd: int gcd =...
  • 求最大公因子(辗转相除法)。 求任意两个整数M,N最大公因子(M,N)的方法如下: 若 M=N*Q+R,其中: R为余数, 满足 O≤R≤N-1 , 则 (M,N)=(N,R) 且当 R=0时, (M,N)=N。 例如,(1500,550)的求解过程如下: ...
  • 辗转相除法:两个正整数a和b(a&gt;b),它们的最大公约数等于a除以b的余数c和b之间的最大公约数。比如10和25,25除以10商2余5,那么10和25的最大公约数,等同于10和5的最大公约数。 以上代码存在取模运算,...
  • 辗转相除法 #include&lt;stdio.h&gt; int main() { int a,b,r,m,n; scanf("%d%d",&amp;a,&amp;b); m=a,n=b; while(b!=0){//被除数不等于0 r=a%b; a=b; b=r;//下一次被除数为r ...
  • 欧几里德算法又称为辗转相除法,用于计算两个非负整数的最大公约数。 template<typename T> T gcd(const T &a, const T &b) { return b == 0 ? a : gcd(b, a % b); } 参考链接:...
  • 辗转相除法 求最大公约数 问题:线上格点的个数 给定平面上两个格点(格点是指纵横坐标都为整数的点)P1=(x1,y2),P1=(x2,y2)P_1=(x_1,y_2),P_1=(x_2,y_2)P1​=(x1​,y2​),P1​=(x2​,y2​) ,线段P1P2P_1P_2P1​P2​...
  • #include<bits/stdc++.h> using namespace std; int main() { int a,b; cin>>a>>b; if(a<b) swap(a,b); while(a%b!=0) { int c; c=b; b=...
  • 【算法】辗转相除法(欧几里得算法)备注功能介绍原理例如算法分析算法实现 备注 2019/7/30 星期二 高中数学必修三学习了“算法初步”,其中有一个叫做辗转相除的算法,这是一个神奇的算法,可以用来求两正整数的...
  • 欧几里德算法又称辗转相除法,用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理: 定理:gcd(a,b) = gcd(b,a mod b) 其算法用C语言描述为 int gcd(int m, int n) { if (m == 0) return n; if (n =...
  • 辗转相除法详解

    千次阅读 2017-08-13 10:02:12
    欧几里得算法,又称辗转相除法,用于求两个自然数的最大公约数。算法基于数论等式gcd(a,b)=gcd(b,a mod b),其时间复杂度为O(logk),其中k=max(a,b),若k的位数为n,则时间复杂度为O(logn)。时间复杂度的证明比较麻烦...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,803
精华内容 1,121
关键字:

辗转相除的时间复杂度