摘要:這是一個簡單的遞歸函數,你可以使用它來生成數列中指定序號的數值這個函數的問題在于它的執行效率非常低有太多值在遞歸調用中被重新計算。
本章內容銜接上一章 數據結構與算法:二分查找
內容提要
兩種基本數據結構:
數組
常見操作: 數組降維、數組去重
鏈表
遞歸:遞歸是很多算法都使用的一種編程方法
- 如何將問題分成基線條件和遞歸條件
- 分而治之策略解決棘手問題
棧
- 調用棧(call stack)
- 遞歸調用棧
常見排序算法:很多算法僅在數據經過排序后才管用。如二分查找,它只能用于有序元素列表。
- 冒泡排序
- 選擇排序
- 插入排序
- 希爾排序
- 歸并排序
- 快速排序
- 堆排序
- 計數排序
- 桶排序
- 基數排序
需要將數據存儲到內存時,你請求計算機提供存儲空間,計算機給你一個存儲地址。需要存
儲多項數據時,有兩種基本方式——數組和鏈表。但它們并非都適用于所有的情形,因此知道它
們的差別很重要
給出:let arr = [[1, 2, 3], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14]]]], 10, 0]; 需求:降維、去重、排序 做法:Array.from(new Set(arr.flat(Infinity).sort((a, b) => a - b))) 解析如下: 0. arr.flat(Infinity) //直接降維值一維數組。 1. sort //排序就不說了。 2. new Set() //達到去重效果 3. Array.from(上一步輸出的結果) //將上一步結果轉換為數組鏈表 遞歸
遞歸(recursion):程序調用自身的編程技巧。
遞歸滿足2個條件:
有反復執行的過程(調用自身)
有跳出反復執行過程的條件(遞歸出口)
遞歸就是指在定義一個概念和過程時,又用到了本身。
哲學的將, 遞歸的妙用就在,如果一個過程中又包含自身,那么這個過程就可以無窮地展開,不會在有窮的步驟后停止。但是描述這個過程只需要有窮的指令。以有窮表現無窮。
在數學與計算機科學中,是指在函數的定義中使用函數自身的方法。遞歸一詞還較常用于描述以自相似方法重復事物的過程。例如,當兩面鏡子相互之間近似平行時,鏡中嵌套的圖像是以無限遞歸的形式出現的。也可以理解為自我復制的過程。
另外多提一句,遞歸和lambda 演算是兩個與圖靈機等價的計算機理論模型,感興趣的讀者可以去進一步研究,這里不贅述。
由于遞歸函數調用自己,編寫這樣的函數時很容易出錯,導致無限循環。
例:編寫這樣倒計時的函數。
5...4...3...2...1
為此,你可以用遞歸的方式編寫:
const countdown = (i) => { console.log(i) // base case 基準條件 if (i <= 0){ return null } // 隱藏的else是 遞歸條件 countdown(i-1) return null } countdown(5)
編寫遞歸函數時,必須告訴它何時停止遞歸。正因為如此,每個遞歸函數都有兩部分:基線
條件(base case)和遞歸條件(recursive case)。遞歸條件指的是函數調用自己,而基線條件則
指的是函數不再調用自己,從而避免形成無限循環。
可以去掉基準條件執行下代碼:
const countdown = (i) => { console.log(i) // base case 基準條件 // if (i <= 0){ // return null // } // 隱藏的else是 遞歸條件 countdown(i-1) return null } countdown(5)
因為無限循環導致Maximum call stack size exceeded error
n! = n (n-1) (n-2) ... 1(n>0)
// 階乘 const fact = (x) => { if(x === 1) { return 1 } return x * fact(x - 1) } console.log(fact(5))斐波那契數組
斐波那契數列可以定義為以下序列:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …
可以看到,該序列是由前兩項數值相加而成的。這個數列的歷史非常悠久,至少可以追溯 到公元700年。它以意大利數學家列奧納多·斐波那契(Leornardo Fibonacci)的名字命 名,斐波那契在1202年使用這個數列描述理想狀態下兔子的增長。
這是一個簡單的遞歸函數,你可以使用它來生成數列中指定序號的數值
這個函數的問題在于它的執行效率非常低
有太多值在遞歸調用中被重新計算。如果編譯器可以將已經計算的值記錄下來,函
數的執行效率就不會如此差。我們可以使用動態規劃的技巧來設計一個效率更高的算法。
動態規劃的本質其實就是兩點:
自底向上分解子問題
通過變量存儲已經計算過的解
根據上面兩點,我們的斐波那契數列的動態規劃思路:
斐波那契數列從 0 和 1 開始,那么這就是這個子問題的最底層
通過數組來存儲每一位所對應的斐波那契數列的值
二叉樹的最大深度樹的最大深度:該題目來自 Leetcode,題目需要求出一顆二叉樹的最大深度
/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * @param {TreeNode} root * @return {number} */ var maxDepth = function(root) { if(!root) return 0 return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1 };
對于該遞歸函數可以這樣理解:一旦沒有找到節點就會返回 0,每彈出一次遞歸函數就會加一,樹有三層就會得到 3。
但是遞歸真的很慢
我們可以寫一個函數 用以遞歸的快速計算
// memoize 全局函數:用以階乘,斐波那契數組等遞歸調用的快速計算 // useage: const memoizeFibonacci = memoize(fibonacci); memoizeFibonacci(45) export function memoize(fn) { const cache = {}; return function () { const key = JSON.stringify(arguments); var value = cache[key]; if (!value) { value = [fn.apply(this, arguments)]; // 放在一個數組中,方便應對undefined,null等異常情況 cache[key] = value; } return value[0]; } }
Stack Overflow上說的一句話:“如果使用循環,程序的性能可能更高;如果使用遞歸,程序可能棧
更容易理解。如何選擇要看什么對你來說更重要。” Recursion or Iteration?
棧是一個線性結構,在計算機中是一個相當常見的數據結構。
棧的特點是只能在某一端添加或刪除數據,遵循先進后出的原則
js實現每種數據結構都可以用很多種方式來實現,其實可以把棧看成是數組的一個子集,所以這里使用數組來實現
快速排序 冒泡排序 Python實現arr = [2,3,6,5,33,7,23] def bubbleSort(arr): for i in range(1, len(arr)): for j in range(0, len(arr)-i): if arr[j] > arr[j+i]: arr[j],arr[j + i] = arr[j + i], arr[j] return arr print(bubbleSort(arr))選擇排序 Python實現
arr = [2,3,6,5,33,7,23] def selectionSort(arr): for i in range(len(arr) - 1): # 記錄最小的索引 minIndex = i for j in range(i + 1, len(arr)): if arr[j] < arr[minIndex]: minIndex = j # i 不是最小數時, 將i 和最小數進行交換 if i != minIndex: arr[i], arr[minIndex] = arr[minIndex], arr[i] return arr print(selectionSort(arr))插入排序 Python實現
arr = [2,3,6,5,33,7,23] def insertionSort(arr): for i in range(len(arr)): preIndex = i-1 current = arr[i] while preIndex >= 0 and arr[preIndex] > current: arr[preIndex+1] = arr[preIndex] preIndex-=1 arr[preIndex+1] = current return arr print(insertionSort(arr))希爾排序 Python實現
arr = [2,3,6,5,33,7,23] def shellSort(arr): import math gap = 1 while(gap < len(arr)/3): gap = gap*3 + 1 while gap > 0: for i in range(gap, len(arr)): temp = arr[i] j = i - gap while j >= 0 and arr[j] >temp: arr[j+gap] = arr[j] j-=gap arr[j+gap] = temp gap = math.floor(gap/3) return arr print(shellSort(arr))
下一篇文章 數據結構與算法:二叉樹算法
參考JS-Sorting-Algorithm
javascript描述數據結構與算法(改自imooc)
算法圖解
常見算法js實現
javascript-algorithms
排序算法總結
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/41324.html
摘要:這是一個簡單的遞歸函數,你可以使用它來生成數列中指定序號的數值這個函數的問題在于它的執行效率非常低有太多值在遞歸調用中被重新計算。 本章內容銜接上一章 數據結構與算法:二分查找 內容提要 兩種基本數據結構: 數組 常見操作: 數組降維、數組去重 鏈表 遞歸:遞歸是很多算法都使用的一種編程方法 - 如何將問題分成基線條件和遞歸條件 - 分而治之策略解決棘手問題 ...
摘要:數據結構常見數據結構數組是最簡單而且應用最廣泛的數據結構特征使用連續內存空間來存儲存放相同類型或著衍生類型的元素數組比較特別,可以存放八種數據類型通過下標來訪問集合特征保存不重復的元素字典特征就是關聯數組,以形式存儲棧,與隊列相似特征存儲數 數據結構 常見數據結構 Array 數組是 最簡單 而且 應用最廣泛 的數據結構 特征: 1、使用連續內存空間來存儲 2、存放相同類型或著衍生類型...
摘要:下面會介紹的一種排序算法快速排序甚至被譽為世紀科學和工程領域的十大算法之一。我們將討論比較排序算法的理論基礎并中借若干排序算法和優先隊列的應用。為了展示初級排序算法性質的價值,我們來看一下基于插入排序的快速的排序算法希爾排序。 前言 排序就是將一組對象按照某種邏輯順序重新排列的過程。比如信用卡賬單中的交易是按照日期排序的——這種排序很可能使用了某種排序算法。在計算時代早期,大家普遍...
摘要:多練練排序算法,不僅能夠讓我們知道一些排序方法的底層實現細節,更能夠鍛煉我們的思維,提升編程能力。排序算法的穩定性一個穩定的排序,指的是在排序之后,相同元素的前后順序不會被改變,反之就稱為不穩定。 1. 導言 因為這是排序算法系列的第一篇文章,所以多啰嗦幾句。 排序是很常見的算法之一,現在很多編程語言都集成了一些排序算法,比如Java 的Arrays.sort()方法,這種方式讓我們可...
摘要:目錄常見的八種排序常見的八種排序直接插入排序直接插入排序希爾排序希爾排序直接選擇排序直接選擇排序堆排序堆排序冒泡排序冒泡排序快速排序快速排序版本版本挖坑法挖坑法前后指針版前后指針版快速排序代碼 目錄 常見的八種排序 直接插入排序 希爾排序 直接選擇排序 堆排序 冒泡排序? 快速排序 hoar...
閱讀 1625·2021-09-22 15:25
閱讀 1506·2021-09-07 10:06
閱讀 3183·2019-08-30 15:53
閱讀 1090·2019-08-29 13:12
閱讀 3373·2019-08-29 13:07
閱讀 725·2019-08-28 18:19
閱讀 2269·2019-08-27 10:57
閱讀 982·2019-08-26 13:29