算法中的遞歸分析和分治法的原理

分析遞歸算法三種方法

替換法、迭代法、通用法（master method）

作用：分析遞歸算法的運行時間

分治算法

將一個問題分解為與原問題相似但規模更小的若干子問題，遞歸地解這些子問題，然后將這些子問題的解結合起來構成原問題的解。這種方法在每層遞歸上均包括三個步驟：

divide（分解）：將問題劃分為若干個子問題

conquer（求解）：遞歸地解這些子問題；若子問題Size足夠小，則直接解決之

Combine（組合）：將子問題的解組合成原問題的解

其中的第二步很關鍵：遞歸調用或直接求解  （遞歸終結條件），且有的算法“分解”容易，有的則“組合”容易

分治法舉例：

歸并排序

①分解：把n個待排序元素劃分為兩個Size為n/2的子序列

②求解：遞歸調用歸并排序將這兩個子序列排序，若子序列長度為1時，已自然有序，無需做任何事情（直接求解）

③組合：將這兩個已排序的子序列合并為一個有序的序列

顯然，分解容易（一分為二），組合難。

快速排序 

剛剛分析過了，快速排序是樞軸記錄劃分，也就是分解難，但是組合易。   A[1…k-1] ≤ A[k] ≤ A[k+1…n]

分治算法分析

設T(n)是Size為n的執行時間，若Size足夠小，如n ≤ C (常數)，則直接求解的時間為θ(1)

①設完成劃分的時間為D(n)

②設分解時，劃分為a個子問題，每個子問題為原問題的1/b，則解各子問題的時間為aT(n/b)

③設組合時間C(n)

一般地，遞歸的求解劃分，而解遞歸式時可忽略細節

①假定函數參數為整數，如

②邊界條件可忽略，當n較小時，T(n）= θ(1)

因為這些細節一般只影響常數因子的大小，不改變量級。求解時，先忽略細節，然后再決定其是否重要！

分析的方法

替換法

猜測解，用數學歸納法確定常數C，證明解正確，關鍵步驟是用猜測的解代入到遞歸式中。

做出好的猜測（沒有一般方法，只能憑經驗）

①與見過的解類似，則猜測之。

②先證較寬松的上、下界，減小猜測范圍。

細節修正

有時猜測解是正確的，但數學歸納法卻不能直接證明其細節，這是因為數學歸納法不是強大到足以證明其細節。這時可從猜測解中減去一個低階項以使數學歸納法得以滿足

避免陷阱

與求和式的數學歸納法類似，證明時漸近記號的使用易產生錯誤。

變量變換

有時改動變量能使未知遞歸式變為熟悉的式子。例如：

迭代法

展開：無須猜測，展開遞歸式，使其成為僅依賴于n和邊界條件的和式，然后用求和方法定界。需要關注：

1、達到邊界條件所需的迭代次數

2、迭代過程中的和式。若在迭代過程中已估計出解的形式，亦可用替換法

3、當遞歸式中包含floor和ceiling函數時，常假定參數n為一個整數次冪，以簡化問題。

遞歸樹

使展開過程直觀化

例： T(n)=2T(n/2)+n^2   （不妨設n=2k）

The master method（通用法，萬能法）

可迅速求解

T(n)=aT(n/b)+f(n)   //常數a ≥1, b>1, f(n)漸近正

意義：將Size為n的問題劃分為a個子問題，每個子問題Size為n/b。每個子問題的時間為T(n/b)，劃分和combine的時間為f(n)。

注意：n/b不一定為整數，應為n/b或n/b，不會影響漸近界。

關于遞歸和循環的理解與比較

遞歸通俗的說就是一個函數調用函數自己（本身），這個調用過程叫遞歸，遞歸是一把雙刃劍（有時方便，有時不好），新航道雅思培訓如果需要處理重復的需要多次計算的問題，通?？梢赃x擇用遞歸或者循環兩種方式，但是遞歸的執行效率不如循環語句。

注意：必須設置終止遞歸的條件檢測，否則慎用。

 up_and_down(););  up_and_down(, n, & (n < + , n, &

首先，main函數用參數1調用遞歸函數，遞歸函數形參n=1，打印語句level1……然后，n<4，故函數本身使用參數n+1=2,第二次調用自己，這樣就打印了level2……

以此類推，當執行到第四級調用，n=4，if失效，不再調用函數，而是執行了第二句打印，先輸出LEVEL4……此時第四級調用結束，控制權返回給了主調函數，也就是第三級主調函數，此函數中上一句是if語句，已經執行完畢，然后繼續執行第二句打印語句，輸出LEVEL3……第三級調用結束，返回控制權給調用函數（也就是第二級主調函數），然后第二級函數開始繼續執行，以此類推，打印LEVEL2,1……

遞歸的基本原理

每一級遞歸都使用自己這一級的私有變量n，同級調用時的地址和返回的地址是一樣的。好好揣摩！

這是函數自己在一層層的往深度調用自己，然后一層層的往回返，每到一層，就繼續執行接下來的語句（故調用開始的地址和返回的地址一樣），而每一級遞歸都是用自己的局部變量。也就是第一級的n不同于第二級的n，這樣子，函數逐步調用然后逐步返回直到main函數里。

遞歸函數里，遞歸語句之前的語句和各級被調的遞歸函數執行順序一致，而遞歸語句之后的語句和被調的遞歸函數執行順序相反（這一特點針對涉及反向順序的編程問題很有用） 

遞歸函數必須包含可以終止的條件，因為遞歸可以替代循環，故必須有終止

尾遞歸

最簡單的遞歸：遞歸語句放到函數末尾，恰在return語句前，叫做tail recursion（尾遞歸），因為出現在函數尾部，作用相當于一條循環語句。

//計算階乘（遞歸和循環）
#include <stdio.h>#include <stdlib.h>//計算階乘int factorial(int);int loopFactorial(int);int main()
{    int num;
    printf("輸入1-12的整數，q退出\n");    while (scanf_s("%d", &num))
    {        if (num < 0)
        {
            printf("error!輸入1-12的整數!");
        }        else if (num > 12)
        {
            printf("輸入1-12的整數!");
        }        else
        {
            printf("\n%d的階乘=%d", num, factorial(num));
            printf("\n%d的階乘=%d", num, loopFactorial(num));
        }
        printf("\n輸入1-12的整數");
    }
    system("pause");    return 0;
}

//循環計算階乘int factorial(int n)
{    int temp;    for (temp = 1; n > 1; n--)
    {
        temp *= n;
    }    return temp;
}

//使用遞歸計算階乘int loopFactorial(int n)
{    int temp;    if (n > 0)
    {
        temp = n * loopFactorial(n - 1);//屬于尾遞歸，如n>0那么這就是最后一句    }    else
    {
        temp = 1;//必須要有遞歸結束判斷條件！    }    return temp;
}

注意:整型范圍，32位機器，int類型最大到21多億，再大的話，就要用long long或者double類型，一般來說，選擇循環比較好些，遞歸每次調用都要有自己的變量集合，占據內存大，每次都要存儲新的變量集合到堆棧，這樣速度慢，但是遞歸（最簡單的是尾遞歸）比較簡單。一些情況還是要用。