Python遞歸時間復雜度
遞歸也是常見算法之一,其時間復雜度一般認為O(logn),但遞歸算法的時間復雜度本質上是要看: 遞歸的次數(shù) * 每次遞歸中的操作次數(shù)
舉例面試題:求x的n次方
思路一: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遞歸內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!
相關文章
python圖像處理-利用一行代碼實現(xiàn)灰度圖摳圖
這篇文章主要介紹了python圖像處理-利用一行代碼實現(xiàn)灰度圖摳圖,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2022-05-05Django 實現(xiàn) Websocket 廣播、點對點發(fā)送消息的代碼
這篇文章主要介紹了Django 實現(xiàn) Websocket 廣播、點對點發(fā)送消息,本文通過實例代碼給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-06-06Python使用itertools模塊實現(xiàn)排列組合功能示例
這篇文章主要介紹了Python使用itertools模塊實現(xiàn)排列組合功能,涉及Python基于itertools模塊product、permutations與combinations_with_replacement方法進行排列、組合等相關操作實現(xiàn)技巧,需要的朋友可以參考下2018-07-07Python將8位的圖片轉為24位的圖片實現(xiàn)方法
這篇文章主要介紹了Python將8位的圖片轉為24位的圖片的實現(xiàn)代碼,非常不錯,具有一定的參考借鑒價值,需要的朋友可以參考下2018-10-10