時間復(fù)雜度、遞歸、尾調(diào)用— (讀文筆記)

susheng 發(fā)布于2019-08-23 14:34 / 2801人閱讀

摘要：遞歸算法是一種直接或者間接調(diào)用自身函數(shù)或者方法的算法。因此，分治策略一般用來解決子問題相互對立的問題，稱為標(biāo)準(zhǔn)分治，而動態(tài)規(guī)劃用來解決子問題重疊的問題。調(diào)用棧尾遞歸和手動優(yōu)化尾調(diào)用就是一個函數(shù)執(zhí)行的最后一步是將另外一個函數(shù)調(diào)用并返回。

輸出

斐波那契數(shù)列的四種寫法

讀參考文章列表

算法復(fù)雜度中的O(logN)底數(shù)是多少

從斐波那契數(shù)列談?wù)劥a的性能優(yōu)化

冰與火之歌：時間與空間復(fù)雜度

看動畫輕松理解遞歸與動態(tài)規(guī)劃

JavaScript調(diào)用棧、尾遞歸和手動優(yōu)化

數(shù)據(jù)結(jié)構(gòu)與算法公開課

問自己幾個問題

算法復(fù)雜度中的O(logN)底數(shù)是多少， log2N 和 log10N 有區(qū)別么？

復(fù)習(xí)時間復(fù)雜度、空間復(fù)雜度、時間復(fù)雜度從小到大

時間復(fù)雜度級數(shù)

循環(huán)與級數(shù)的關(guān)系

分治、遞歸，遞歸的時間復(fù)雜度

從一個數(shù)組中找出最大的兩個數(shù)

什么是動態(tài)規(guī)劃，時間復(fù)雜度多少

尾調(diào)用和普通調(diào)用有啥不一樣

問題解答

1，常底數(shù)是無所謂的，logaN/logbN = logab, 是一個常數(shù)

2，時間復(fù)雜度：
代碼段執(zhí)行次數(shù)累加

空間復(fù)雜度：
除了輸入本身所占的空間之外，用于計算的所必須的空間量

時間復(fù)雜度從小到大
O(1)所以，O(n) 能否優(yōu)化 O(logn)?優(yōu)化關(guān)鍵

3，Ep12 時間復(fù)雜度級數(shù)
算數(shù)級數(shù)，與末項平房同階，
1+2+3+...n = O(n^2)

冪方級數(shù)，比冪次高出一階：
1+2^2+3^2+4^2 +... n^2 = O(n^3);
1+2^3+3^3+4^3 +... n^3= O(n^4);
1+2^4+3^4+4^4+... n^4 = O(n^5);

幾何級數(shù)（a>1）:與末項同階
a^0+a^1+a^2+... a^n = (a^(n+1) - 1)/(a-1) = O(a^n)
1+2+4+8 +... 2^n = 2^(n+1) -1 = O(2^n)

4，循環(huán)與級數(shù)的關(guān)系

    for(let i = 0; i < n; i++)
    for(let j = 0; i < n; j++)  坐標(biāo)軸形成正方形，O(n^2)
     
    for(let i = 0; i < n; i++)
    for(let j = 0; i < j; j++)  坐標(biāo)軸形成三角形，O(n^2)

5，冰與火之歌：時間與空間復(fù)雜度

分治：將原問題分解為若干個規(guī)模較小但類似于原問題的子問題（Divide），「遞歸」的求解這些子問題（Conquer），然后再合并這些子問題的解來建立原問題的解。

遞歸算法是一種直接或者間接調(diào)用自身函數(shù)或者方法的算法。通俗來說，遞歸算法的實質(zhì)是把問題分解成規(guī)模縮小的同類問題的子問題，然后遞歸調(diào)用方法來表示問題的解。它有如下特點(diǎn)：

1. 一個問題的解可以分解為幾個子問題的解 
2. 這個問題與分解之后的子問題，除了數(shù)據(jù)規(guī)模不同，求解思路完全一樣 
3. 存在遞歸終止條件，即必須有一個明確的遞歸結(jié)束條件，稱之為遞歸出口

遞歸算法的世界復(fù)雜度，得分好幾種
第一種：
遞歸中進(jìn)行一次遞歸調(diào)用的復(fù)雜度分析，如：二分查找法
不管怎么樣，最多調(diào)用了一次遞歸調(diào)用而已，這時候時間復(fù)雜度看什么時候跳出遞歸

第二種：
遞歸中進(jìn)行多次遞歸調(diào)用的復(fù)雜度分析
比如說斐波拉契數(shù)列，多次調(diào)用自身
所以時間復(fù)雜度等于遞歸樹中節(jié)點(diǎn)數(shù)總和，就是代碼計算的調(diào)用次數(shù)。

T(n) = 各層遞歸實例所需時間之和
= O(1) * (2^0 + 2 ^1 + ...2^n)
= O(1) * (2^(n+1) - 1)
= O(2^n)

空間復(fù)雜度：
一個程序執(zhí)行時除了需要存儲空間和存儲本身所使用的指令、常數(shù)、變量和輸入數(shù)據(jù)外，還需要一些對數(shù)據(jù)進(jìn)行操作的工作單元和存儲一些為現(xiàn)實計算所需信息的輔助空間。

6，從一個數(shù)組中找出最大的兩個數(shù)
算法一
先遍歷一遍，找出最大值的位置，x1，時間復(fù)雜度為 n-1
再遍歷一遍，從剩下的n-2個數(shù)中，找最大值，時間復(fù)雜度為 n-2
總共 O(2n-3) = O(n)

算法二
x1是小值，x2是大數(shù)
如果值比x2大，替換x2
如果 x1時間復(fù)雜度O(n)

算法三
左邊找最大L1，右邊找最大 R1
L1else, 要么找左邊第二大

7，看動畫輕松理解遞歸與動態(tài)規(guī)劃
動態(tài)規(guī)劃能解決的問題分治策略肯定能解決，只是運(yùn)行時間長了。因此，分治策略一般用來解決子問題相互對立的問題，稱為標(biāo)準(zhǔn)分治，而動態(tài)規(guī)劃用來解決子問題重疊的問題。

將「動態(tài)規(guī)劃」的概念關(guān)鍵點(diǎn)抽離出來描述就是這樣的：

1.動態(tài)規(guī)劃法試圖只解決每個子問題一次
2.一旦某個給定子問題的解已經(jīng)算出，則將其記憶化存儲，以便下次需要同一個子問題解之時直接查表。

8.JavaScript調(diào)用棧、尾遞歸和手動優(yōu)化
尾調(diào)用：
就是一個函數(shù)執(zhí)行的最后一步是將另外一個函數(shù)調(diào)用并返回。

一般來說，如果方法a調(diào)用方法b, 那么b放到棧頂，棧指針指向棧頂, 當(dāng)前幀是b, 調(diào)用幀是a,

當(dāng)函數(shù)B執(zhí)行完成后，還需要將執(zhí)行權(quán)返回A，那么函數(shù)A內(nèi)部的變量，調(diào)用函數(shù)B的位置等信息都必須保存在調(diào)用幀A中。不然，當(dāng)函數(shù)B執(zhí)行完繼續(xù)執(zhí)行函數(shù)A時，就會亂套。
那么現(xiàn)在，我們將函數(shù)B放到了函數(shù)A的最后一步調(diào)用（即尾調(diào)用），那還有必要保留函數(shù)A的棧幀么？當(dāng)然不用，因為之后并不會再用到其調(diào)用位置、內(nèi)部變量。因此直接用函數(shù)B的棧幀取代A的棧幀即可。當(dāng)然，如果內(nèi)層函數(shù)使用了外層函數(shù)的變量，那么就仍然需要保留函數(shù)A的棧幀，典型例子即是閉包。

總得來說，如果所有函數(shù)的調(diào)用都是尾調(diào)用，那么調(diào)用棧的長度就會小很多，這樣需要占用的內(nèi)存也會大大減少。這就是尾調(diào)用優(yōu)化的含義。

// 尾調(diào)用錯誤示范1.0
function f(x){
  let y = g(x);
  return y;
}

// 尾調(diào)用錯誤示范2.0
function f(x){
  return g(x) + 1;
}
// 尾調(diào)用錯誤示范3.0
function f(x) {
  g(x); // 這一步相當(dāng)于g(x) return undefined
}

1.0最后一步為賦值操作，2.0最后一步為加法運(yùn)算操作，3.0隱式的有一句return undefined