(1)&

林甸網(wǎng)站制作公司哪家好，找成都創(chuàng)新互聯(lián)！從網(wǎng)頁設(shè)計、網(wǎng)站建設(shè)、微信開發(fā)、APP開發(fā)、響應(yīng)式網(wǎng)站建設(shè)等網(wǎng)站項目制作，到程序開發(fā)，運(yùn)營維護(hù)。成都創(chuàng)新互聯(lián)成立與2013年到現(xiàn)在10年的時間，我們擁有了豐富的建站經(jīng)驗和運(yùn)維經(jīng)驗，來保證我們的工作的順利進(jìn)行。專注于網(wǎng)站建設(shè)就選成都創(chuàng)新互聯(lián)。
nbsp;遞歸執(zhí)行過程
   例子：求N!。
    這是一個簡單的"累乘"問題，用遞歸算法也能解決。
    n! = n * (n - 1)!   n > 1
    0! = 1, 1! = 1      n = 0,1
    因此，遞歸算法如下：

Java代碼
fact(int n) {
    if(n == 0 || n == 1)
         return 1;
        else
             return n * fact(n - 1);
    }
    以n=3為例，看運(yùn)行過程如下：
    fact(3) ----- fact(2) ----- fact(1) ------ fact(2) -----fact(3)
    ------------------------------>  ------------------------------>
                遞歸                            回溯
  遞歸算法在運(yùn)行中不斷調(diào)用自身降低規(guī)模的過程，當(dāng)規(guī)模降為1，即遞歸到fact(1)時，滿足停止條件停止遞歸，開始回溯(返回調(diào)用算法)并計算，從fact(1)=1計算返回到fact(2);計算2*fact(1)=2返回到fact(3)；計算3*fact(2)=6，結(jié)束遞歸。
   算法的起始模塊也是終止模塊。
(2) 遞歸實現(xiàn)機(jī)制
    每一次遞歸調(diào)用，都用一個特殊的數(shù)據(jù)結(jié)構(gòu)"棧"記錄當(dāng)前算法的執(zhí)行狀態(tài)，特別地設(shè)置地址棧，用來記錄當(dāng)前算法的執(zhí)行位置，以備回溯時正常返回。遞歸模塊的形式參數(shù)是普通變量，每次遞歸調(diào)用得到的值都是不同的，他們也是由"棧"來存儲。
(3) 遞歸調(diào)用的幾種形式
    一般遞歸調(diào)用有以下幾種形式(其中a1、a2、b1、b2、k1、k2為常數(shù))。
   <1> 直接簡單遞歸調(diào)用： f(n) {...a1 * f((n - k1) / b1); ...};

   <2> 直接復(fù)雜遞歸調(diào)用： f(n) {...a1 * f((n - k1) / b1); a2 * f((n - k2) / b2); ...};
    <3> 間接遞歸調(diào)用：  f(n) {...a1 * f((n - k1) / b1); ...}，
                        g(n) {...a2 * f((n - k2) / b2); ...}。
2. 遞歸算法效率分析方法
   遞歸算法的分析方法比較多，最常用的便是迭代法。
  迭代法的基本步驟是先將遞歸算法簡化為對應(yīng)的遞歸方程，然后通過反復(fù)迭代，將遞歸方程的右端變換成一個級數(shù)，最后求級數(shù)的和，再估計和的漸進(jìn)階。
  <1> 例：n!
       算法的遞歸方程為： T(n) = T(n - 1) + O(1);
       迭代展開： T(n) = T(n - 1) + O(1)
                       = T(n - 2) + O(1) + O(1)
                       = T(n - 3) + O(1) + O(1) + O(1)
                       = ......
                       = O(1) + ... + O(1) + O(1) + O(1)
                       = n * O(1)
                       = O(n)
      這個例子的時間復(fù)雜性是線性的。
<2> 例：如下遞歸方程：

      T(n) = 2T(n/2) + 2, 且假設(shè)n=2的k次方。
      T(n) = 2T(n/2) + 2
           = 2(2T(n/2*2) + 2) + 2
           = 4T(n/2*2) + 4 + 2
           = 4(2T(n/2*2*2) + 2) + 4 + 2
           = 2*2*2T(n/2*2*2) + 8 + 4 + 2
           = ...
           = 2的(k-1)次方 * T(n/2的(i-1)次方) + $(i:1~(k-1))2的i次方
           = 2的(k-1)次方 + (2的k次方)  - 2
           = (3/2) * (2的k次方) - 2
           = (3/2) * n - 2
           = O(n)
      這個例子的時間復(fù)雜性也是線性的。
<3> 例：如下遞歸方程：

      T(n) = 2T(n/2) + O(n), 且假設(shè)n=2的k次方。
      T(n) = 2T(n/2) + O(n)
           = 2T(n/4) + 2O(n/2) + O(n)
           = ...
           = O(n) + O(n) + ... + O(n) + O(n) + O(n)
           = k * O(n)
           = O(k*n)
           = O(nlog2n) //以2為底

      一般地，當(dāng)遞歸方程為T(n) = aT(n/c) + O(n), T(n)的解為：
      O(n)          (a<c && c>1)
      O(nlog2n)     (a=c && c>1) //以2為底
      O(nlogca)     (a>c && c>1) //n的(logca)次方，以c為底
   上面介紹的3種遞歸調(diào)用形式，比較常用的是第一種情況，第二種形式也有時出現(xiàn)，而第三種形式(間接遞歸調(diào)用)使用的較少，且算法分析
比較復(fù)雜。 下面舉個第二種形式的遞歸調(diào)用例子。
  <4> 遞歸方程為：T(n) = T(n/3) + T(2n/3) + n
     為了更好的理解，先畫出遞歸過程相應(yīng)的遞歸樹：
                            n                        --------> n
                    n/3            2n/3              --------> n
              n/9       2n/9   2n/9     4n/9         --------> n
           ......     ......  ......  .......        ......
                                                     --------
                                                     總共O(nlogn)
     累計遞歸樹各層的非遞歸項的值，每一層和都等于n，從根到葉的最長路徑是：

      n --> (2/3)n --> (4/9)n --> (12/27)n --> ... --> 1
     設(shè)最長路徑為k，則應(yīng)該有：

     (2/3)的k次方 * n = 1
     得到 k = log(2/3)n  // 以(2/3)為底
     于是 T(n) <= (K + 1) * n = n (log(2/3)n + 1)
     即 T(n) = O(nlogn)
    由此例子表明，對于第二種遞歸形式調(diào)用，借助于遞歸樹，用迭代法進(jìn)行算法分析是簡單易行的。

分享名稱：【轉(zhuǎn)】遞歸函數(shù)時間復(fù)雜度分析-創(chuàng)新互聯(lián)
鏈接URL：http://chinadenli.net/article4/deshoe.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供全網(wǎng)營銷推廣、網(wǎng)站排名、自適應(yīng)網(wǎng)站、響應(yīng)式網(wǎng)站、域名注冊、面包屑導(dǎo)航

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)