Python 官方文档：入门教程 => 点击学习
目录思路一：for循环思路二：递归递归也是常见算法之一，其时间复杂度一般认为O(logn)，但递归算法的时间复杂度本质上是要看: 递归的次数 * 每次递归中的操作次数 举例面试题：求
递归也是常见算法之一，其时间复杂度一般认为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))到此这篇关于python递归时间复杂度的文章就介绍到这了,更多相关Python递归内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！
--结束END--
本文标题: Python递归时间复杂度
本文链接: https://www.lsjlt.com/news/142996.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑，方便收藏和打印～
2024-03-01
2024-03-01
2024-03-01
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
官方手机版
微信公众号
商务合作
0