为什么正常的重复乘法算法效率不高？

Question

作为问题,我不明白为什么我们需要一些算法,如指数通过平方或模幂运算来计算数字的幂.

例如,我有一个重复的乘法算法,如下所示:

def expt_mul(a, n):
    r = 1
    for i in xrange(n):
        r *= a
    return r

a乘以n倍,因此复杂度为O(n),为什么效率不高？

Answer 1

例如,在加密中,通常进行取幂,其中指数可以是2 ¹⁰⁰或更多的量级.假设你每秒可以进行10 ^10次乘法运算,那么你所说的需要大约10 ²⁰秒.用这种方式表达,你可能会耸耸肩说"那么什么？",所以让我们把它转换成年份:10 ²⁰秒/ 3600秒/小时/ 24小时/天/ 365.25天/年/ 14E9年/当前宇宙年龄=>超过现在宇宙年龄的226倍!与对数时间算法形成对比,对数时间算法将在几百次操作中进行2 ^100次求幂 - 几乎可以从您的角度进行瞬时计算.