首页 > 代码库 > 高效率的取幂运算,递归解法跟非递归解法
高效率的取幂运算,递归解法跟非递归解法
long int Pow( long int x, unsigned int n ) { // 求幂运算 if( n == 0 ) return 1; if( n == 1 ) return x; if( n % 2 == 0 ) return Pow( x * x, n / 2 ); else return Pow( x, n - 1 ) * x; // 可以用下列的注释行替换 //return Pow( x * x, n / 2 ) * x; }
上面的是递归解法,时间复杂度为 O(logN) ;
下面用两种非递归的解法来进行快速的取幂运算
第一种:
long int Pow( long int x, unsigned int n ) { // 求幂运算 int y, mul, temp; if( n == 0 ) return 1; if( n == 1 ) return x; y = x, mul = 1; while( n > 1 ) { if( n % 2 == 0 ) { temp = y * y; y = temp; n = n / 2; } else { mul *= y; n = n - 1; } } y = mul * y; return y; }
第二种:
long int Pow( long int x, unsigned int n ) { // 求幂运算 int y, mul, temp; if( n == 0 ) return 1; if( n == 1 ) return x; y = x, mul = 1; while( n > 1 ) { if( n % 2 == 0 ) { temp = y * y; y = temp; n = n / 2; } else { mul = mul * y; temp = y * y; y = temp; n = n / 2; } } y = mul * y; return y; }
高效率的取幂运算,递归解法跟非递归解法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。