加载中…
个人资料
裴大帅2020
裴大帅2020
  • 博客等级:
  • 博客积分:0
  • 博客访问:688,206
  • 关注人气:63
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

power(x,N)函数logN时间复杂度的解法

(2019-08-27 23:01:18)
标签:

算法

杂谈

分类: 编程技术
       如果我们需要求解power(x,N)函数logN时间复杂度的解法,如果x * x * x... 进行N次操作显然是人人皆知的方法,其时间复杂度为O(N),有没有更快的方法解决此类问题。下面介绍的方法其时间复杂度为O(logN)。
      假设N=10,则power(x,N)函数logN时间复杂度的解法,而10的二进制表示为1010,所以power(x,N)函数logN时间复杂度的解法
      对1010这4位,将x一直做自乘操作,则这4位分别位于:
power(x,N)函数logN时间复杂度的解法

      所以power(x,N)函数logN时间复杂度的解法 只需要取序号第2和第4位的乘积即可。扩展成power(x,N)函数logN时间复杂度的解法,则将N转化为二进制数。假设二进制数总共有M位,则x只需自乘M次,其中N二进制对应为1的自乘值取出来,最后相乘即得到power(x,N)函数logN时间复杂度的解法的结果。
     算法示例如下:

object BigPower {

  def main(args: Array[String]) = {
    val result = powN(2, 10)
    println(result)
  }

  def powN(x: Int, N: Int): Int = {
    var tmp = x
    var result = 1
    var Ncopy = N
    while(Ncopy != 0){
      if((Ncopy & 1) != 0){
        result = result * tmp
      }
      tmp = tmp * tmp
      Ncopy = Ncopy >> 1
    }
    result
  }
}



0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有