前端需要知道的數據結構與算法(持續更新中...)

Jensen 發布于2019-08-23 15:17 / 3033人閱讀

摘要：通常需要在實際的計算機運行才知道具體的執行時間。算法的執行時間往往和算法代碼中語句執行的數量有關。空間復雜度運行一段程序的內存占用，空間復雜度通常指的是算法程序在計算機只想中只想所需要的存儲空間。

基本數據結構 JS 數據類型

基本類型（棧 stack）： Number String Boolean Null Undefined 和 Symbol（es6 新增）
引用類型（堆 heap）：Object Array Function Data

數據結構

數據結構是指相互之間存在著一種或多種關系的數據元素的集合和該集合中數據元素之間的關系組成

算法 算法特征

有窮性、確定性、可行性、輸入、輸出

算法設計衡量

正確性、可讀性、健壯性, 時間復雜度, 空間復雜度

時間復雜度

運行一段程序的計算工作量，時間復雜度即通常所說的算法執行所需要耗費的時間，時間越短，算法越好。但是，一個算法的執行時間往往無法精確估計。通常需要在實際的計算機運行才知道具體的執行時間。但是，也可以大致進行估計，得到算法的時間復雜度。算法的執行時間往往和算法代碼中語句執行的數量有關。

空間復雜度

運行一段程序的內存占用，空間復雜度通常指的是算法程序在計算機只想中只想所需要的存儲空間。

eg:

O(1):常數運算

O(n):1 層循環

O(n^2):2 層循環

O(n^n):n 層循環

O(log2n):int i = 1, n = 100;while(i < n){ i = i * 2;}

算法分類

快速排序算法

深度優先算法

廣度優先算法

堆排序算法

歸并排序算法

冒泡排序

原理：每次把最大或者最小的浮到最頂層

let arr = [33, 1, 46, 23, 35, 12, 30, 4, 16, 2]
function bubbleSort(array) {
  for (var i = 0; i < array.length; i++) {
    for (var j = 0; j < array.length - i - 1; j++) {
      if (array[j] > array[j + 1]) {
        var temp = array[j]
        array[j] = array[j + 1]
        array[j + 1] = temp
      }
    }
  }
  return array
}

插入排序

原理：從數組的第二個和第一個比較，如果小于第一個則插入到第一個元素之前，否則不變
第三個一次和第二個第一個比,如果小于第二個且大于第一個則插入第二個元素之前

let arr = [33, 1, 46, 23, 35, 12, 30, 4, 16, 2]
function insertionSort(arr) {
  var len = arr.length
  var preIndex, current
  for (var i = 1; i < len; i++) {
    preIndex = i - 1
    current = arr[i]
    while (preIndex >= 0 && arr[preIndex] > current) {
      arr[preIndex + 1] = arr[preIndex]
      preIndex--
    }
    arr[preIndex + 1] = current
  }
  return arr
}

選擇排序

原理：從數組的第一個開始，向后比較，找到最小的和第一個交換

let arr = [33, 1, 46, 23, 35, 12, 30, 4, 16, 2]
function selectionSort(arr) {
  var len = arr.length
  var minIndex, temp
  for (var i = 0; i < len; i++) {
    minIndex = i
    for (var j = i + 1; j < len; j++) {
      if (arr[minIndex] > arr[j]) {
        minIndex = j
      }
    }
    temp = arr[i]
    arr[i] = arr[minIndex]
    arr[minIndex] = temp
  }
  return arr
}

算法復雜度

排序方法	時間復雜度（最壞）	時間復雜度（最好）	空間復雜度	穩定性	復雜性
冒泡排序	O(n^2)	O(n)	O(1)	穩定	簡單
插入排序	O(n^2)	O(n)	O(1)	穩定	簡單
選擇排序	O(n^2)	O(n^2)	O(1)	不穩定	簡單

參考

前端你應該了解的數據結構與算法

如何理解時間復雜度和空間復雜度 3. 時間復雜度和空間復雜度

GPU云服務器云服務器描述的數據結構與算法前端需要的技術前端需要掌握的技術前端開發需要掌握的技術

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

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

平時積累的前端資源，持續更新中。。。

本文收集學習過程中使用到的資源。持續更新中…… 項目地址 https://github.com/abc-club/f... 目錄 vue react react-native Weex typescript Taro nodejs 常用庫 css js es6 移動端微信公眾號小程序 webpack GraphQL 性能與監控高質文章趨勢動效數據結構與算法 js core 代碼規范...

acrazing 2019-08-26 10:40 評論0 收藏0
前端面試題收集，持續更新中

摘要：對于所訪問的每個元素，函數應該將該元素傳遞給所提供的回調函數。 HTML 在線閱讀Github地址題目列表 HTML HTML和XHTML的區別 Html的語義化 Doctype的文檔類型 cookie、sessionSttorage、localStory區別 HTML全局屬性(global attribute)有哪些？常見的瀏覽器內核有哪些？介紹一下你對瀏覽器內核的理解？...

kgbook 2019-08-22 16:49 評論0 收藏0
前端面試題收集，持續更新中

摘要：對于所訪問的每個元素，函數應該將該元素傳遞給所提供的回調函數。 HTML 在線閱讀Github地址題目列表 HTML HTML和XHTML的區別 Html的語義化 Doctype的文檔類型 cookie、sessionSttorage、localStory區別 HTML全局屬性(global attribute)有哪些？常見的瀏覽器內核有哪些？介紹一下你對瀏覽器內核的理解？...

2json 2019-08-29 15:12 評論0 收藏0
前端面試題收集，持續更新中

摘要：對于所訪問的每個元素，函數應該將該元素傳遞給所提供的回調函數。 HTML 在線閱讀Github地址題目列表 HTML HTML和XHTML的區別 Html的語義化 Doctype的文檔類型 cookie、sessionSttorage、localStory區別 HTML全局屬性(global attribute)有哪些？常見的瀏覽器內核有哪些？介紹一下你對瀏覽器內核的理解？...

adam1q84 2019-08-02 10:17 評論0 收藏0
校招社招必備核心前端面試問題與詳細解答

摘要：本文總結了前端老司機經常問題的一些問題并結合個人總結給出了比較詳盡的答案。網易阿里騰訊校招社招必備知識點。此外還有網絡線程，定時器任務線程，文件系統處理線程等等。線程核心是引擎。主線程和工作線程之間的通知機制叫做事件循環。 showImg(https://segmentfault.com/img/bVbu4aB?w=300&h=208); 本文總結了前端老司機經常問題的一些問題并結合個...

jonh_felix 2019-08-23 18:40 評論0 收藏0