公告:欢迎访问,查看更多资源请点我^.^!            点我关闭广告
学习笔记~欧几里得和幂次运算
2018-09-11 16:27:19
1173人阅读
评论(0)
分类:算法

    /**
* 欧几里得算法,计算最大公因数,可以理解为数学中的辗转相除法
* @param x
* @param y
* @return
* @desc 时间复杂度为O(logN)
*/
private static long gcd(long x, long y) {
while (y != 0) { // y == 0 时候才被整除得到最大公约数x
long temp = x % y;
x = y;
y = temp;
}
return x;
}

/**
* 幂次运算
* @param x
* @param n
* @return * @desc 时间复杂度为O(logN) */
private static long pow(long x, long n) {
if (n == 0) {
return 1;
}
if (n == 1) {
return x;
}
if (n % 2 == 0) {
// 效率相较于pow2该行低一些 因为此方法中多增加了一个递归调用,增加了时间和空间复杂度
return pow(x, n / 2) * pow (x, n / 2);
} else {
return x * pow(x, (n - 1) / 2) * pow(x, (n - 1) / 2);
}
}


/**
* 幂次运算
* @param x
* @param n
* @return
*/
private static long pow2(long x, long n) {
if (n == 0) {
return 1;
}
if (n == 1) {
return x;
}
if (n % 2 == 0) {
return pow(x * x, n / 2);
} else {
return x * pow(x * x, n / 2);
}
}


分享一下:
赞一下(0)
博主资料
博主头像
zc521106
文章:34
浏览:19899
文章分类
Java(12)
NoSql(112)
数据库(12)
前端(12)
阅读排行
Java基础知识
(12)
NoSql应用
(112)
数据库Oracle语法
(12)
前端常用工具类
(12)
java web项目
(12)
linux安装mysql
(12)
评论区
这篇文章怎么样?写点评论吧!
姓名:
邮箱:
有回复时通知我:
发表
回复【10.20.30.32】:
暂无评论,快抢沙发!
* 以上用户言论只代表其个人观点,不代表iBlog网站的观点或立场,如有任何疑问请随时联系管理员...