欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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

 更新時間：2022年03月18日 11:07:07   作者：chen_沖沖  
這篇文章主要介紹了Python遞歸時間復(fù)雜度，時間復(fù)雜度一般認(rèn)為O(logn)，但遞歸算法的時間復(fù)雜度本質(zhì)上是要看遞歸的次數(shù)，每次遞歸中的操作次數(shù)，下面文章詳細(xì)介紹，需要的朋友可以參考一下

遞歸也是常見算法之一，其時間復(fù)雜度一般認(rèn)為O(logn)，但遞歸算法的時間復(fù)雜度本質(zhì)上是要看: 遞歸的次數(shù) * 每次遞歸中的操作次數(shù)

舉例面試題：求x的n次方

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

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

最新評論