Python遞歸時間復雜度

更新時間：2022年03月18日 11:07:07 作者：chen_沖沖

這篇文章主要介紹了Python遞歸時間復雜度，時間復雜度一般認為O(logn)，但遞歸算法的時間復雜度本質(zhì)上是要看遞歸的次數(shù)，每次遞歸中的操作次數(shù)，下面文章詳細介紹，需要的朋友可以參考一下

思路一：for循環(huá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))

思路二：遞歸

但是遞歸時間復雜度未必更優(yōu)，

比如：

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))

如果面試官詢問是否還可以優(yōu)化？可思考的方向是遞歸模塊提取出來。

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遞歸內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章:

python游戲開發(fā)之視頻轉(zhuǎn)彩色字符動畫
這篇文章主要為大家詳細介紹了python游戲開發(fā)之視頻轉(zhuǎn)彩色字符動畫，具有一定的參考價值，感興趣的小伙伴們可以參考一下
2019-04-04
Python3實現(xiàn)將本地JSON大數(shù)據(jù)文件寫入MySQL數(shù)據(jù)庫的方法
這篇文章主要介紹了Python3實現(xiàn)將本地JSON大數(shù)據(jù)文件寫入MySQL數(shù)據(jù)庫的方法,涉及Python針對json大數(shù)據(jù)文件的逐行讀取、mysql數(shù)據(jù)庫寫入等相關操作技巧,需要的朋友可以參考下
2018-06-06
python繼承threading.Thread實現(xiàn)有返回值的子類實例
這篇文章主要介紹了python繼承threading.Thread實現(xiàn)有返回值的子類實例，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧
2020-05-05
Python面向?qū)ο缶幊讨畢^(qū)間的插入詳解
這篇文章主要為大家詳細介紹了Python面向?qū)ο缶幊虒嵗坛讨械膮^(qū)間的插入，文中的示例代碼講解詳細，對我們學習Python有一定幫助，需要的可以參考一下
2022-08-08
python如何利用joblib保存訓練模型
這篇文章主要介紹了python如何利用joblib保存訓練模型問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教
2023-06-06
Python中優(yōu)雅處理JSON文件的方法實例
JSON是一種輕量級的數(shù)據(jù)交換格式,JSON采用完全獨立于語言的文本格式，但是也使用了類似于C語言家族的習慣,這篇文章主要給大家介紹了關于Python中優(yōu)雅處理JSON文件的相關資料,需要的朋友可以參考下
2021-12-12
python通過函數(shù)名調(diào)用函數(shù)的幾種方法總結(jié)
今天帶大家學習的是怎么使用python通過函數(shù)名調(diào)用函數(shù),文中對python通過函數(shù)名調(diào)用函數(shù)的幾種方法有非常詳細的介紹,需要的朋友可以參考下
2021-06-06
Python3 requests模塊如何模仿瀏覽器及代理
這篇文章主要介紹了Python3 requests模塊如何模仿瀏覽器及代理,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
2020-06-06
python 利用openpyxl讀取Excel表格中指定的行或列教程
這篇文章主要介紹了python 利用openpyxl讀取Excel表格中指定的行或列教程，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧
2021-02-02
Python bytes string相互轉(zhuǎn)換過程解析
這篇文章主要介紹了Python bytes string相互轉(zhuǎn)換過程解析,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
2020-03-03