時間復雜度、遞歸、尾調用— (讀文筆記)

susheng 發布于2019-08-23 14:34 / 2808人閱讀

摘要：遞歸算法是一種直接或者間接調用自身函數或者方法的算法。因此，分治策略一般用來解決子問題相互對立的問題，稱為標準分治，而動態規劃用來解決子問題重疊的問題。調用棧尾遞歸和手動優化尾調用就是一個函數執行的最后一步是將另外一個函數調用并返回。

輸出

斐波那契數列的四種寫法

讀參考文章列表

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

從斐波那契數列談談代碼的性能優化

冰與火之歌：時間與空間復雜度

看動畫輕松理解遞歸與動態規劃

JavaScript調用棧、尾遞歸和手動優化

數據結構與算法公開課

問自己幾個問題

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

復習時間復雜度、空間復雜度、時間復雜度從小到大

時間復雜度級數

循環與級數的關系

分治、遞歸，遞歸的時間復雜度

從一個數組中找出最大的兩個數

什么是動態規劃，時間復雜度多少

尾調用和普通調用有啥不一樣

問題解答

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

2，時間復雜度：
代碼段執行次數累加

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

時間復雜度從小到大
O(1)所以，O(n) 能否優化 O(logn)?優化關鍵

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

冪方級數，比冪次高出一階：
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);

幾何級數（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，循環與級數的關系

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

5，冰與火之歌：時間與空間復雜度

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

遞歸算法是一種直接或者間接調用自身函數或者方法的算法。通俗來說，遞歸算法的實質是把問題分解成規?？s小的同類問題的子問題，然后遞歸調用方法來表示問題的解。它有如下特點：

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

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

第二種：
遞歸中進行多次遞歸調用的復雜度分析
比如說斐波拉契數列，多次調用自身
所以時間復雜度等于遞歸樹中節點數總和，就是代碼計算的調用次數。

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

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

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

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

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

7，看動畫輕松理解遞歸與動態規劃
動態規劃能解決的問題分治策略肯定能解決，只是運行時間長了。因此，分治策略一般用來解決子問題相互對立的問題，稱為標準分治，而動態規劃用來解決子問題重疊的問題。

將「動態規劃」的概念關鍵點抽離出來描述就是這樣的：

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

8.JavaScript調用棧、尾遞歸和手動優化
尾調用：
就是一個函數執行的最后一步是將另外一個函數調用并返回。

一般來說，如果方法a調用方法b, 那么b放到棧頂，棧指針指向棧頂, 當前幀是b, 調用幀是a,

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

總得來說，如果所有函數的調用都是尾調用，那么調用棧的長度就會小很多，這樣需要占用的內存也會大大減少。這就是尾調用優化的含義。

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

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

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

云服務器 GPU云服務器尾調用時間復雜度遞歸調用快速排序時間復雜度

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/100804.html

尾調用優化——記一道面試題的思考

摘要：如果函數內部還調用函數，那就還有一個的調用幀，依次類推。等同于等同于如果所有函數都是尾調用，那么完全可以做到每次執行時，調用幀只有一項，這將大大節省內存。這就是尾調用優化。尾遞歸函數調用自身，稱為遞歸。前言面某東，有一道題目是實現一個斐波拉契數列，已知第一項為0，第二項為1，第三項為1，后一項是前兩項之和，即f(n) = f(n - 1) + f(n -2)。拿到這個題目，二...

awkj 2019-08-22 17:00 評論0 收藏0
js 實現斐波那契數列(數組緩存、動態規劃、尾調用優化)

摘要：根據該規則，返回第個斐波那契數。尾遞歸函數調用自身，稱為遞歸。一個前端眼中的斐波那契數列解斐波那契數列的實用解法調用棧尾遞歸和手動優化尾調用優化譯我從用寫斐波那契生成器中學到的令人驚訝的件事斐波那契數列是以下一系列數字： 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ... 在種子數字 0 和 1 ...

趙連江 2019-08-23 11:38 評論0 收藏0
基于CPS變換的尾遞歸轉換算法

摘要：一個解決的辦法是從算法上解決，把遞歸算法改良成只依賴于少數狀態的迭代算法，然而此事知易行難，線性遞歸還容易，樹狀遞歸就難以轉化了，而且并不是所有遞歸算法都有非遞歸實現。前言眾所周知，遞歸函數容易爆棧，究其原因，便是函數調用前需要先將參數、運行狀態壓棧，而遞歸則會導致函數的多次無返回調用，參數、狀態積壓在棧上，最終耗盡?？臻g。一個解決的辦法是從算法上解決，把遞歸算法改良成只依賴于少...

supernavy 2019-08-20 14:35 評論0 收藏0
尾調用和尾遞歸

摘要：執行完了，銷毀調用棧中自己的記錄，依次銷毀和的調用幀，最后完成整個流程。尾遞歸定義先來看一下遞歸，當一個函數調用自身，就叫做遞歸。尾調用 1. 定義尾調用是函數式編程中一個很重要的概念，當一個函數執行時的最后一個步驟是返回另一個函數的調用，這就叫做尾調用。注意這里函數的調用方式是無所謂的，以下方式均可：函數調用: func(···) 方法調用: obj.meth...

goji 2019-08-22 16:09 評論0 收藏0
Vue源碼解析：虛擬dom比較原理

摘要：算法子節點比較這部分代碼比較多，先說說原理后面再貼代碼。循環結束的標志就是舊子節點數組或新子節點數組遍歷完，即。第二步尾尾比較。第三步頭尾比較。第四步尾頭比較。節點確認后，真實序列為，未確認序列為第五次是均不相似，直接插入到未確認序列頭部。通過對 Vue2.0 源碼閱讀，想寫一寫自己的理解，能力有限故從尤大佬2016.4.11第一次提交開始讀，準備陸續寫：模版字符串轉AST語法...

Towers 2019-08-23 15:19 評論0 收藏0