def x_n(x,n):
? ? """
? ? 時間復(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))

思路二：遞歸

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

比如：

def x_n(x,n):
? ? """
? ? 時間復(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):
? ? """
? ? 時間復(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):
? ? """
? ? 時間復(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遞歸時間復(fù)雜度的文章就介紹到這了,更多相關(guān)Python遞歸內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章:

相關(guān)文章

python圖像處理-利用一行代碼實現(xiàn)灰度圖摳圖
這篇文章主要介紹了python圖像處理-利用一行代碼實現(xiàn)灰度圖摳圖，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教
2022-05-05
Django 實現(xiàn) Websocket 廣播、點(diǎn)對點(diǎn)發(fā)送消息的代碼
這篇文章主要介紹了Django 實現(xiàn) Websocket 廣播、點(diǎn)對點(diǎn)發(fā)送消息,本文通過實例代碼給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下
2020-06-06
用Python生成HTML表格的方法示例
這篇文章主要介紹了用Python生成HTML表格的方法示例，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
2020-03-03
Python使用itertools模塊實現(xiàn)排列組合功能示例
這篇文章主要介紹了Python使用itertools模塊實現(xiàn)排列組合功能,涉及Python基于itertools模塊product、permutations與combinations_with_replacement方法進(jìn)行排列、組合等相關(guān)操作實現(xiàn)技巧,需要的朋友可以參考下
2018-07-07
Python中print()函數(shù)使用實例詳解
Python的print()函數(shù)可以打印輸出，常用來將內(nèi)容打印到控制臺，print()是python中最常見的一個函數(shù)，本文就通過一些實例來給大家講講如何使用print()函數(shù),需要的朋友可以參考下
2023-07-07
Python將8位的圖片轉(zhuǎn)為24位的圖片實現(xiàn)方法
這篇文章主要介紹了Python將8位的圖片轉(zhuǎn)為24位的圖片的實現(xiàn)代碼，非常不錯，具有一定的參考借鑒價值,需要的朋友可以參考下
2018-10-10
Python3爬蟲學(xué)習(xí)之將爬取的信息保存到本地的方法詳解
這篇文章主要介紹了Python3爬蟲學(xué)習(xí)之將爬取的信息保存到本地的方法,結(jié)合實例形式詳細(xì)分析了Python3信息爬取、文件讀寫、圖片存儲等相關(guān)操作技巧,需要的朋友可以參考下
2018-12-12
Python從臨時郵箱獲取驗證碼的操作代碼
這篇文章主要介紹了Python從臨時郵箱獲取驗證碼的操作代碼,本文通過實例代碼給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下
2023-08-08
Python3.遍歷某文件夾提取特定文件名的實例
下面小編就為大家分享一篇Python3.遍歷某文件夾提取特定文件名的實例，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧
2018-04-04
在Python中實現(xiàn)替換字符串中的子串的示例
今天小編就為大家分享一篇在Python中實現(xiàn)替換字符串中的子串的示例，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧
2018-10-10