上述代码的时间复杂度为O( logN ),O(N)到O(logN)已经是很大的进步了,但是,还能优化吗?显然可以,上述算法依然是一个递归算法,那其必然也存在递归的通病,容易栈溢出。
3.3 优化中的优化
好吧,我们依然用解决斐波那契数列的思路来解决这题, 递归转为递推,为表示方便以 f[N] 表示M的N次方的值,我们从f[0]开始计算一直计算到f[N]。
f[0] = 1 , f[1] = M , f[2] = f[1] * f[1] , f[3] = f[2] * f[1] , f[4] = f[2] * f[2] , ........
写着写着发现有点不对劲,哪里不对劲呢?f[4]需要用到f[3]的值吗?f[N]需要用到f[N-1],f[N-2],直到f[N/2+1]的值吗?我们显然做了很多无效计算,也存储了很多我们显然不需要的值。
So, 问题又转换为:给你一个数N,如何在递推中判断是否该存储遇到的值。
这里懒得写公式了,就copy下编程之美上的解释:
分析:
以一个通项为例当ak(即n在二进制表示中的第K位)为0时,其值为1,不需要任何计算,当ak等于1时,我们需要将之前的乘积再乘以来得到A^n。而显然
本文地址:http://dh99988.xhstdz.com/news/778.html
物流园资讯网 http://dh99988.xhstdz.com/ , 查看更多