原文链接:https://programmercarl.com/
def function1(x, n): if n==0: return 1 else: return function1(x, n-1)*x
该方法的时间复杂度为O(n)
def function2(x, n): if n==0: return 1 if n%2==1: return function2(x, n/2) * function(x, n/2) * x else: return function2(x, n/2) * function(x, n/2)
该方法的时间复杂度依旧在O(n)
def function3(x, n): if n==0: return 1 t = function3(x, n/2) if n%2==1: return t*t*x else: return t*t
该方法将第二种的多次递归改成t的一次递归,如此便将时间复杂度降低到了O(log^n)