日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

Python遞歸時間復雜度_python

作者：chen_沖沖 ? 更新時間： 2022-05-21 編程語言

遞歸也是常見算法之一，其時間復雜度一般認為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))

原文鏈接：https://blog.csdn.net/q339179198/article/details/123560095

欄目分類
最近更新