遞歸算法時(shí)間復(fù)雜度的分析，小編來(lái)舉例說(shuō)明。大家來(lái)看一下這道面試題：求x的n次方

大家想一下這么簡(jiǎn)單的一道題目代碼應(yīng)該如何寫(xiě)。

最直觀的方式應(yīng)該就是，一個(gè)for循環(huán)求出結(jié)果，代碼如下

int function1(int x, int n) {
    int result = 1;  // 注意 任何數(shù)的0次方等于1
    for (int i = 0; i < n; i++) {
        result = result * x;
    }
    return result;
}

時(shí)間復(fù)雜度為O(n)

此時(shí)面試官會(huì)說(shuō)，有沒(méi)有效率更好的算法呢。

如果同學(xué)們此時(shí)沒(méi)有思路，建議不要說(shuō)：我不會(huì)，我不知道。可以和面試官探討一下，問(wèn)：可不可以給點(diǎn)提示。

面試官一般會(huì)提示：考慮一下遞歸算法

有的同學(xué)就寫(xiě)出了如下這樣的一個(gè)遞歸的算法，使用遞歸解決了這個(gè)問(wèn)題

int function2(int x, int n) {
    if (n == 0) {
        return 1; // return 1 同樣是因?yàn)?次方是等于1的
    }
    return function2(x, n - 1) * x;
}

面試官問(wèn)：那么這份代碼的時(shí)間復(fù)雜度是多少?

有的同學(xué)可能一看到遞歸就想到了logn，其實(shí)并不是這樣

遞歸算法的時(shí)間復(fù)雜度本質(zhì)上是要看: 遞歸的次數(shù) * 每次遞歸中的操作次數(shù)

那我們?cè)賮?lái)看代碼，我們遞歸了幾次呢。

每次n-1，遞歸了n次 時(shí)間復(fù)雜度是O(n)，每次進(jìn)行了一個(gè)乘法操作，乘法操作的時(shí)間復(fù)雜度一個(gè)常數(shù)項(xiàng)O(1)

所以這份代碼的時(shí)間復(fù)雜度是 n * 1 = O(n)

這個(gè)時(shí)間復(fù)雜度可能就沒(méi)有達(dá)到面試官的預(yù)期。

于是同學(xué)又寫(xiě)出了這樣的一個(gè)遞歸的算法的代碼如下 ，來(lái)求 x的n次方

int function3(int x, int n) {
    if (n == 0) {
        return 1;
    }
    if (n % 2 == 1) {
        return function3(x, n/2) * function3(x, n/2)*x;
    }
    return function3(x, n/2) * function3(x, n/2);
}

面試官看到后微微一笑，問(wèn)這份代碼的時(shí)間復(fù)雜度又是多少呢?

我們來(lái)分析一下

首先看遞歸了多少次呢，可以把遞歸的次數(shù) 抽象出一顆滿二叉樹(shù)。

我們剛剛寫(xiě)的這個(gè)算法，可以用一顆滿二叉樹(shù)來(lái)表示(為了方便表示 我選擇n為偶數(shù))，如圖：

當(dāng)前這顆二叉樹(shù)就是求x的n次方，n為16的情況

n為16的時(shí)候 我們進(jìn)行了多少次乘法運(yùn)算呢

這棵樹(shù)上每一個(gè)節(jié)點(diǎn)就代表著一次遞歸并進(jìn)行了一次相乘操作

所以 進(jìn)行了多少次遞歸的話，就是看這棵樹(shù)上有多少個(gè)節(jié)點(diǎn)。

熟悉二叉樹(shù)的同學(xué)應(yīng)該知道如何求滿二叉樹(shù)節(jié)點(diǎn)數(shù)量

這顆滿二叉樹(shù)的節(jié)點(diǎn)數(shù)量就是2^3 + 2^2 + 2^1 + 2^0 = 15

有同學(xué)就會(huì)發(fā)現(xiàn) 這其實(shí)是等比數(shù)列的求和公式， 如果不理解的同學(xué)可以直接記下來(lái)這個(gè)結(jié)論。

這個(gè)結(jié)論在二叉樹(shù)相關(guān)的面試題里也經(jīng)常出現(xiàn)。

這么如果是求x的n次方，這個(gè)遞歸樹(shù)有多少個(gè)節(jié)點(diǎn)呢，如下圖所示

時(shí)間復(fù)雜度忽略掉常數(shù)項(xiàng)-1之后，我們發(fā)現(xiàn)這個(gè)遞歸算法的時(shí)間復(fù)雜度依然是O(n)。

此時(shí)面試官就會(huì)問(wèn)， 貌似這個(gè)遞歸的算法依然還是O(n)啊， 很明顯沒(méi)有達(dá)到面試官的預(yù)期

那么在思考一下 O(logn)的遞歸算法應(yīng)該怎么寫(xiě)

這里在提示一下 上面剛剛給出的那份遞歸算法的代碼，是不是有哪里比較冗余呢。

來(lái)看這份優(yōu)化后的遞歸算法代碼

int function4(int x, int n) {
    if (n == 0) {
        return 1;
    }
    int t = function4(x, n/2);// 這里相對(duì)于function3，是把這個(gè)遞歸操作抽取出來(lái)
    if (n % 2 == 1) {
        return t*t*x;
    }
    return t*t;
}

那我們看一下 時(shí)間復(fù)雜度是多少

依然還是看他遞歸了多少次

我們可以看到 這里僅僅有一個(gè)遞歸調(diào)用，且每次都是 n/2

所以這里我們一共調(diào)用了 log以2為底n的對(duì)數(shù)次

每次遞歸了做都是一次乘法操作，這也是一個(gè)常數(shù)項(xiàng)的操作，

所以說(shuō)這個(gè)遞歸算法的時(shí)間復(fù)雜度才是真正的O(logn)。

以上就是關(guān)于“遞歸算法時(shí)間復(fù)雜度的分析”介紹，大家如果對(duì)此比較感興趣，想了解更多相關(guān)知識(shí)，不妨來(lái)關(guān)注一下本站的Java算法視頻教程，里面的課程內(nèi)容細(xì)致全面，通俗易懂，很適合沒(méi)有基礎(chǔ)的小伙伴學(xué)習(xí)，希望對(duì)大家能夠有所幫助。