Python递归时间复杂度
短信预约 -IT技能 免费直播动态提醒
递归也是常见算法之一，其时间复杂度一般认为O(logn)，但递归算法的时间复杂度本质上是要看: 递归的次数 * 每次递归中的操作次数
举例面试题：求x的n次方
思路一：for循环
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))到此这篇关于Python递归时间复杂度的文章就介绍到这了,更多相关Python递归内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！
免责声明：
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
