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

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

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

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

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

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

3个回答

复杂度是logN

算了一下,logN

为什么是logN呢?求问大神们具体的计算步骤啊,谢谢

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!