算法导论中N的M次幂（python）
数值的整数次方
http://www.nowcoder.com/questionTerminal/1a834e5e3e1a4b7ba251417554e07c00
思路：如果遍历累乘的话，时间复杂度为O(n)，
但是用递归的话可以做到O(logn)的复杂度
举个栗子：
2^8 = 2^4 * 2^4
2^4=2^2 * 2^2
2^2 = 2 * 2
需要注意的两种情况
是当指数为0的时候，直接返回1
当指数为负数的时候，去绝对值，返回 1/result
耗时比遍历快了进10毫秒
# -*- coding:utf-8 -*-
class Solution:
def Power(self, base, exponent):
# write code here
if exponent == 0:
return 1
if exponent < 0:
return 1/self.mi(base, abs(exponent))
return self.mi(base, exponent)
def mi(self,base,exponent):
if exponent == 1:
return base
if exponent%2:
return base * self.mi(base,exponent/2)*self.mi(base,exponent/2)
else:
return self.mi(base,exponent/2)*self.mi(base,exponent/2)
查看13道真题和解析