首页 > 代码库 > Thinking in scala (8)---- 乘幂计算
Thinking in scala (8)---- 乘幂计算
递归的方式：
b^n = (b^(n/2))^2 若n是偶数
b^n = b*(b^(n-1)) 若n是奇数
迭代的方式
product：存储中间结果,初始化为1
b^n = (b^2)^(n/2) * product 若n是偶数
b^n = b^(n-1) * product*b 若n是奇数
递归方式比较简单，这里不再贴上实现的代码，下面是用迭代方式计算乘幂的Scala代码：
object expt{ def f(b:Int,n:Int,product:Int):Int={ if(n==1) b*product else if(isOdd(n)) f(b,n-1,b*product) else f(b*b,n/2,product) } def isOdd(n:Int)={ n%2 == 1 } def expt(b:Int,n:Int)=f(b,n,1) def main(args:Array[String])= { println(expt(2,10)) println(expt(2,11)) println(expt(5,9)) }}
无论是递归算法还是迭代算法，时间复杂度都是O(lg(n))，递归算法的空间复杂度是O(lg(n))，迭代算法的空间复杂度是O(1)
Thinking in scala (8)---- 乘幂计算
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。