怎么理解大數(shù)據(jù)中x的n次冪函數(shù)

發(fā)布時間：2021-12-09 10:36:40 來源：億速云閱讀：289 作者：柒染欄目：大數(shù)據(jù)

怎么理解大數(shù)據(jù)中x的n次冪函數(shù)，很多新手對此不是很清楚，為了幫助大家解決這個難題，下面小編將為大家詳細(xì)講解，有這方面需求的人可以來學(xué)習(xí)下，希望你能有所收獲。

題目描述

編輯一個函數(shù)，計算x的n次冪。如：輸入2.00000，10，輸出9.26100。

題解

雖然編程語言中都有現(xiàn)成的冪運算符號，但這道題目要求我們自己寫一個完成該功能的函數(shù)。x的n次冪，就是n個x相乘，可以通過for循環(huán)實現(xiàn)該目的，時間復(fù)雜度為O(N)，如何把時間復(fù)雜度降到O(logN)，是該題重點。

思路：遞歸、自治算法

定義該函數(shù)為pow(x,n)，如果要計算2的10次冪（pow(2，10)），相當(dāng)于計算2的5次冪乘以2的5次冪（pow(2,5)*pow(2,5)），2的5次冪又等于2的2次冪乘以2的2次冪乘以2 （pow(2,2)*pow(2,2)*2），以此類推，發(fā)現(xiàn)這個問題可以用遞歸解決，并且每次只需要計算一半的數(shù)據(jù)，直到n為0作為遞歸的出口。這樣就可以把時間復(fù)雜度降到O(logN)。每次計算一半的思想類似于二分法，二分法也是典型的時間復(fù)雜度為O(logN)的算法，因此應(yīng)建立O(logN)與二分法的思維關(guān)聯(lián) 。

    class Solution:    def myPow(self, x: float, n: int) -> float:        def pow(m):            if m==0:                return 1.0            else :                tmp = pow(m//2)                if m%2==0:                    return tmp*tmp                else :                    return tmp*tmp*x        if n>=0:            return pow(n)        else:            return 1.0/pow(-n)

看完上述內(nèi)容是否對您有幫助呢？如果還想對相關(guān)知識有進(jìn)一步的了解或閱讀更多相關(guān)文章，請關(guān)注億速云行業(yè)資訊頻道，感謝您對億速云的支持。

向AI問一下細(xì)節(jié)

怎么理解大數(shù)據(jù)中x的n次冪函數(shù)

猜你喜歡

最新資訊

相關(guān)推薦

相關(guān)標(biāo)簽