Python遞歸時(shí)間復(fù)雜度

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

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

思路一：for循環(huán)

def x_n(x,n):
? ? """
? ? 時(shí)間復(fù)雜度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))

思路二：遞歸

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

比如：

def x_n(x,n):
? ? """
? ? 時(shí)間復(fù)雜度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):
? ? """
? ? 時(shí)間復(fù)雜度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):
? ? """
? ? 時(shí)間復(fù)雜度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))

到此這篇關(guān)于Python遞歸時(shí)間復(fù)雜度的文章就介紹到這了,更多相關(guān)Python遞歸內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章:

相關(guān)文章

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