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

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

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

輸出

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

讀參考文章列表

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

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

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

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

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

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

問自己幾個(gè)問題

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

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

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

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

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

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

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

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

問題解答

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

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

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

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

3，Ep12 時(shí)間復(fù)雜度級數(shù)
算數(shù)級數(shù)，與末項(xiàng)平房同階，
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）:與末項(xiàng)同階
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，冰與火之歌：時(shí)間與空間復(fù)雜度

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

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

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

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

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

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

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

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

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

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

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

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

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

8.JavaScript調(diào)用棧、尾遞歸和手動(dòng)優(yōu)化
尾調(diào)用：
就是一個(gè)函數(shù)執(zhí)行的最后一步是將另外一個(gè)函數(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時(shí)，就會(huì)亂套。
那么現(xiàn)在，我們將函數(shù)B放到了函數(shù)A的最后一步調(diào)用（即尾調(diào)用），那還有必要保留函數(shù)A的棧幀么？當(dāng)然不用，因?yàn)橹蟛⒉粫?huì)再用到其調(diào)用位置、內(nèi)部變量。因此直接用函數(shù)B的棧幀取代A的棧幀即可。當(dāng)然，如果內(nèi)層函數(shù)使用了外層函數(shù)的變量，那么就仍然需要保留函數(shù)A的棧幀，典型例子即是閉包。

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

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

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

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

GPU云服務(wù)器云服務(wù)器尾調(diào)用時(shí)間復(fù)雜度遞歸調(diào)用快速排序時(shí)間復(fù)雜度

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/100804.html

發(fā)表評論

登陸后可評論

0條評論

susheng

男|高級講師

我要關(guān)注我要私信

TA的文章

tensorflow.keras

閱讀 540·2023-04-25 14:26
子網(wǎng)劃分

閱讀 1295·2021-11-25 09:43
云虛擬主機(jī)如何關(guān)閉-如何重啟和關(guān)閉云虛擬主機(jī)？

閱讀 3489·2021-09-22 15:25
從輸入U(xiǎn)RL到頁面展示

閱讀 1458·2019-08-30 15:54
動(dòng)態(tài)生成DOM元素的高度及行數(shù)獲取與計(jì)算方法

閱讀 533·2019-08-30 12:57
騰訊云IM-SDK集成（web端）完成IM登錄

閱讀 778·2019-08-29 17:24
前端碎語（1）

閱讀 3174·2019-08-28 18:13
CSS固定高度或?qū)挾葍?nèi)容超出后自動(dòng)增加的辦法

閱讀 2696·2019-08-28 17:52

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

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

相關(guān)文章

**尾調(diào)用優(yōu)化——記一道面試題的思考**

**js 實(shí)現(xiàn)斐波那契數(shù)列(數(shù)組緩存、動(dòng)態(tài)規(guī)劃、尾調(diào)用優(yōu)化)**

基于CPS變換的尾遞歸轉(zhuǎn)換算法

**尾調(diào)用和尾遞歸**

Vue源碼解析：虛擬dom比較原理

發(fā)表評論

0條評論

susheng

男|高級講師

TA的文章

tensorflow.keras

子網(wǎng)劃分

云虛擬主機(jī)如何關(guān)閉-如何重啟和關(guān)閉云虛擬主機(jī)？

從輸入U(xiǎn)RL到頁面展示

動(dòng)態(tài)生成DOM元素的高度及行數(shù)獲取與計(jì)算方法

騰訊云IM-SDK集成（web端）完成IM登錄

前端碎語（1）

CSS固定高度或?qū)挾葍?nèi)容超出后自動(dòng)增加的辦法

最新活動(dòng)

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

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

相關(guān)文章

發(fā)表評論

0條評論

男|高級講師

TA的文章

最新活動(dòng)

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

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