递归也是常见算法之一，其时间复杂度一般认为O(logn)，但递归算法的时间复杂度本质上是要看: 递归的次数 * 每次递归中的操作次数
举例面试题：求x的n次方
def x_n(x,n): """ 时间复杂度O(n) """ if n==0: return 1 return x*x_n(x,n-1) if __name__=='__main__': print(x_n(2,0)) print(x_n(2,3)) print(x_n(2,4))
但是递归时间复杂度未必更优，
比如：
def x_n(x,n): """ 时间复杂度O(n) """ if n==0: return 1 return x*x_n(x,n-1) if __name__=='__main__': print(x_n(2,0)) print(x_n(2,3)) print(x_n(2,4))
也可以是：
def x_n(x,n): """ 时间复杂度O(n) """ if n==0: return 1 if n%2==1: return x*x_n(x,n//2)*x_n(x,n//2) else: return x_n(x,n//2)*x_n(x,n//2) if __name__=='__main__': print(x_n(2,0)) print(x_n(2,3)) print(x_n(2,4))
如果面试官询问是否还可以优化？可思考的方向是递归模块提取出来。
def x_n(x,n):
"""
时间复杂度O(logn)
"""
if n==0:
return 1
t=x_n(x,n//2)
#print("t:",t)
if n%2==1:
return x*t*t
return t*t
if __name__=='__main__':
print(x_n(2,0))
print(x_n(2,3))
print(x_n(2,4))
