yzhq97 2015-08-08 11:33 采纳率: 0%
浏览 1504

一个关于算法复杂度的问题

以下是一个计算a的b次幂的算法:
假定我已有一个质数表,里面包含所有需要用到的质数,并且从小到大排序

 定义函数 幂(a,b):
    如果 b是0:
        返回 1

    质数检查范围 = b的平方根向上取整
    依次取出质数表中的质数:
        如果 质数超出检查范围:
            跳出循环
        如果 质数整除b:
            返回 幂( 幂(a,质数), b/质数 )

    返回 a * 幂( a, b-1 )

这个算法的复杂度应该怎样衡量?

  • 写回答

3条回答 默认 最新

  • threenewbee 2015-08-08 23:08
    关注

    复杂度是logN

    评论

报告相同问题?

悬赏问题

  • ¥15 MATLAB动图问题
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题