資訊專欄INFORMATION COLUMN
摘要：通常需要在實(shí)際的計(jì)算機(jī)運(yùn)行才知道具體的執(zhí)行時(shí)間。算法的執(zhí)行時(shí)間往往和算法代碼中語(yǔ)句執(zhí)行的數(shù)量有關(guān)?？臻g復(fù)雜度運(yùn)行一段程序的內(nèi)存占用，空間復(fù)雜度通常指的是算法程序在計(jì)算機(jī)只想中只想所需要的存儲(chǔ)空間。
基本數(shù)據(jù)結(jié)構(gòu) JS 數(shù)據(jù)類型
基本類型（棧 stack）： Number String Boolean Null Undefined 和 Symbol（es6 新增）
引用類型（堆 heap）：Object Array Function Data
數(shù)據(jù)結(jié)構(gòu)是指相互之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合和該集合中數(shù)據(jù)元素之間的關(guān)系組成
算法 算法特征有窮性、確定性、可行性、輸入、輸出
算法設(shè)計(jì)衡量正確性、可讀性、健壯性, 時(shí)間復(fù)雜度, 空間復(fù)雜度
時(shí)間復(fù)雜度運(yùn)行一段程序的計(jì)算工作量，時(shí)間復(fù)雜度即通常所說(shuō)的算法執(zhí)行所需要耗費(fèi)的時(shí)間，時(shí)間越短，算法越好。但是，一個(gè)算法的執(zhí)行時(shí)間往往無(wú)法精確估計(jì)。通常需要在實(shí)際的計(jì)算機(jī)運(yùn)行才知道具體的執(zhí)行時(shí)間。但是，也可以大致進(jìn)行估計(jì)，得到算法的時(shí)間復(fù)雜度。算法的執(zhí)行時(shí)間往往和算法代碼中語(yǔ)句執(zhí)行的數(shù)量有關(guān)。
空間復(fù)雜度運(yùn)行一段程序的內(nèi)存占用，空間復(fù)雜度通常指的是算法程序在計(jì)算機(jī)只想中只想所需要的存儲(chǔ)空間。
eg:
O(1):常數(shù)運(yùn)算
O(n):1 層循環(huán)
O(n^2):2 層循環(huán)
O(n^n):n 層循環(huán)
O(log2n):int i = 1, n = 100;while(i < n){ i = i * 2;}
算法分類快速排序算法
深度優(yōu)先算法
廣度優(yōu)先算法
堆排序算法
歸并排序算法
冒泡排序原理：每次把最大或者最小的浮到最頂層
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
}
插入排序
原理：從數(shù)組的第二個(gè)和第一個(gè)比較，如果小于第一個(gè)則插入到第一個(gè)元素之前，否則不變
第三個(gè)一次和第二個(gè)第一個(gè)比,如果小于第二個(gè)且大于第一個(gè)則插入第二個(gè)元素之前
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
}
選擇排序
原理：從數(shù)組的第一個(gè)開(kāi)始，向后比較，找到最小的和第一個(gè)交換
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
}
算法復(fù)雜度
| 排序方法 | 時(shí)間復(fù)雜度（最壞） | 時(shí)間復(fù)雜度（最好） | 空間復(fù)雜度 | 穩(wěn)定性 | 復(fù)雜性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n^2) | O(n) | O(1) | 穩(wěn)定 | 簡(jiǎn)單 |
| 插入排序 | O(n^2) | O(n) | O(1) | 穩(wěn)定 | 簡(jiǎn)單 |
| 選擇排序 | O(n^2) | O(n^2) | O(1) | 不穩(wěn)定 | 簡(jiǎn)單 |
前端你應(yīng)該了解的數(shù)據(jù)結(jié)構(gòu)與算法
如何理解時(shí)間復(fù)雜度和空間復(fù)雜度 3. 時(shí)間復(fù)雜度和空間復(fù)雜度
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/101815.html
本文收集學(xué)習(xí)過(guò)程中使用到的資源。 持續(xù)更新中…… 項(xiàng)目地址 https://github.com/abc-club/f... 目錄 vue react react-native Weex typescript Taro nodejs 常用庫(kù) css js es6 移動(dòng)端 微信公眾號(hào) 小程序 webpack GraphQL 性能與監(jiān)控 高質(zhì)文章 趨勢(shì) 動(dòng)效 數(shù)據(jù)結(jié)構(gòu)與算法 js core 代碼規(guī)范...
摘要：對(duì)于所訪問(wèn)的每個(gè)元素，函數(shù)應(yīng)該將該元素傳遞給所提供的回調(diào)函數(shù)。 HTML 在線閱讀Github地址 題目列表 HTML HTML和XHTML的區(qū)別 Html的語(yǔ)義化 Doctype的文檔類型 cookie、sessionSttorage、localStory區(qū)別 HTML全局屬性(global attribute)有哪些？ 常見(jiàn)的瀏覽器內(nèi)核有哪些？ 介紹一下你對(duì)瀏覽器內(nèi)核的理解？...
摘要：對(duì)于所訪問(wèn)的每個(gè)元素，函數(shù)應(yīng)該將該元素傳遞給所提供的回調(diào)函數(shù)。 HTML 在線閱讀Github地址 題目列表 HTML HTML和XHTML的區(qū)別 Html的語(yǔ)義化 Doctype的文檔類型 cookie、sessionSttorage、localStory區(qū)別 HTML全局屬性(global attribute)有哪些？ 常見(jiàn)的瀏覽器內(nèi)核有哪些？ 介紹一下你對(duì)瀏覽器內(nèi)核的理解？...
摘要：對(duì)于所訪問(wèn)的每個(gè)元素，函數(shù)應(yīng)該將該元素傳遞給所提供的回調(diào)函數(shù)。 HTML 在線閱讀Github地址 題目列表 HTML HTML和XHTML的區(qū)別 Html的語(yǔ)義化 Doctype的文檔類型 cookie、sessionSttorage、localStory區(qū)別 HTML全局屬性(global attribute)有哪些？ 常見(jiàn)的瀏覽器內(nèi)核有哪些？ 介紹一下你對(duì)瀏覽器內(nèi)核的理解？...
摘要：本文總結(jié)了前端老司機(jī)經(jīng)常問(wèn)題的一些問(wèn)題并結(jié)合個(gè)人總結(jié)給出了比較詳盡的答案。網(wǎng)易阿里騰訊校招社招必備知識(shí)點(diǎn)。此外還有網(wǎng)絡(luò)線程，定時(shí)器任務(wù)線程，文件系統(tǒng)處理線程等等。線程核心是引擎。主線程和工作線程之間的通知機(jī)制叫做事件循環(huán)。 showImg(https://segmentfault.com/img/bVbu4aB?w=300&h=208); 本文總結(jié)了前端老司機(jī)經(jīng)常問(wèn)題的一些問(wèn)題并結(jié)合個(gè)...
閱讀 2453·2021-09-08 09:45
閱讀 3391·2021-09-08 09:45
閱讀 3131·2019-08-30 15:54
閱讀 3380·2019-08-26 13:54
閱讀 1446·2019-08-26 13:26
閱讀 1412·2019-08-26 13:23
閱讀 942·2019-08-23 17:57
閱讀 2209·2019-08-23 17:14
