JavaScript時間復雜度和空間復雜度

3403771864 發(fā)布于2022-09-25 22:15 / 617人閱讀

　　前言

　　在JS是用來時間復雜度和空間復雜度，時間復雜度和空間復雜度是衡量一個算法是否優(yōu)秀的標準，現(xiàn)在我們就來說手時間復雜度和空間復雜度。

　　時間復雜度和空間復雜度是衡量一個算法是否優(yōu)秀的標準，通常我們比較兩個算法時會用到以下兩種方法：

　　預先估算：首先做出算法設計，在去估算這個算法所需的時間復雜度和空間復雜度，兩者進行比較，擇優(yōu)。

　　事后統(tǒng)計：寫一個可執(zhí)行程序/腳本用來表達兩個算法，交給計算機去執(zhí)行，分別記錄兩個算法所需要的時間復雜度和空間復雜度，然后兩個進行比較，選擇更優(yōu)秀的那個。、

　　通常情況下我們都會采用第一種方式進行對比，因為第二種在不同環(huán)境、不同語言、不同計算機下的運行結果是有差異的，而且第二種的工作量也要比第一種要大。

　　時間復雜度

　　所謂的時間復雜度就是用于定性描述算法所運行需要花費的時間，所謂的定性就是大概進行描述一下運行時間的趨勢，不會去具體到運行需要多少秒；時間復雜度通常用大O來表示，例如O(1)、O(n)、O(logn)等。

　　接下來我們通過具體的代碼來展示一下時間復雜度，這樣更方便去理解：

　　O(1)

　　let i = 0
　　console.log(i)

　　因為在這個代碼中，這兩行代碼永遠只執(zhí)行一次，所以時間復雜度是`O(1)`

　　O(n)

　　for (let i = 0; i < n; i++) {
　　console.log(i)
　　}

　　在上面的代碼中，運行時間取決與`n`，所以時間復雜度是`O(n)`。

　　O(logn)

　　let i = 1
　　while (i < n) {
　　console.log(i)
　　i *= 2
　　}

　　如果是下面這種情況：

　　let i = 0
　　console.log(i)
　　for (let i = 0; i < n; i++) {
　　console.log(n)
　　}

　　它的時間復雜度是O(1) + O(n)，它最終的時間復雜度是O(n)，兩個時間復雜度相加的話一般會忽略較小的那個。

　　如果是兩個時間復雜度相乘的話，例如下面這段代碼：

　　for (let i = 0; i < n; i++) {
　　for (let j = 0; j < n; j++) {
　　console.log(j)
　　}
　　}

　　這段代碼的時間復雜度是O(n^2)，如果是相乘的話會將兩個時間復雜度進行相乘。

　　空間復雜度

　　空間復雜度與時間復雜度差不多，表示的是算法在運行過程中臨時占用存儲空間的大小的一個計量單位，

　　現(xiàn)在我們來看一下幾個例子：

　　O(1)

　　let i = 0
　　console.log(i)

　　因為在這個代碼中，僅僅定義了一個臨時變量，所以空間復雜度是`O(1)`

　　O(n)

　　const arr = []
　　for (let i = 0; i < n; i++) {
　　arr.push(i)
　　}

　　在上面的代碼中，主要想是用來聲明了一個數(shù)組，每循環(huán)一次都要往數(shù)組中存儲一個變量，所以時間復雜度是`O(n)`

　　O(n^2)

　　let i = 1
　　while (i < n) {
　　console.log(i)
　　i *= 2
　　}

　　有關JavaScript時間復雜度和空間復雜度的相關內(nèi)容已講述完畢，希望你獲得更多知識。

GPU云服務器云服務器時間復雜度快速排序時間復雜度最大流算法時間復雜度數(shù)據(jù)結構時間復雜度

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

轉(zhuǎn)載請注明本文地址：http://www.hztianpu.com/yun/127836.html

【javascript系列】時間復雜度和空間復雜度

摘要：第三段，時間復雜度。五空間復雜度分析空間復雜度的話和時間復雜度類似推算。一、前言時間復雜度和空間復雜度，我們在大學里的算法與數(shù)據(jù)結構課程中已經(jīng)學習過，這回根據(jù)項目工作中整理一下，這個估計只是一個粗略的估計分析，并不是一個準確的估計分析。 1、學習時間復雜度和空間復雜度是很有必要的，這個屬于算法與數(shù)據(jù)結構的范疇，學這個是為了解決代碼中的快和省的問題。這樣才能使你的代碼運行效率更高，占...

dcr309duan 2019-08-26 10:18 評論0 收藏0
JavaScript中的算法（附10道面試常見算法題解決方法和思路）

摘要：中的算法附道面試常見算法題解決方法和思路關注每日一道面試題詳解面試過程通常從最初的電話面試開始，然后是現(xiàn)場面試，檢查編程技能和文化契合度。值得記住的數(shù)組方法有和。一個好的解決方案是使用內(nèi)置的方法。 JavaScript中的算法（附10道面試常見算法題解決方法和思路）關注github每日一道面試題詳解 Introduction 面試過程通常從最初的電話面試開始，然后是現(xiàn)場面試，檢查編程...

Cruise_Chan 2019-08-26 10:22 評論0 收藏0
LeetCode 之 JavaScript 解答第一題 —— 兩數(shù)之和（Two Sum）

摘要：步驟遍歷數(shù)組數(shù)據(jù)，將根據(jù)下標和元素值存放到散列表中。目標值減去數(shù)組元素差值并在散列表中查找。測試法三一遍哈希表算法思路遍歷目標值減去數(shù)組元素的差值同時判斷該值在散列表中是否存在差值，如果存在，則返回否則將數(shù)據(jù)加入到散列表中。 Time：2019/4/1Title:Two SumDifficulty: simpleAuthor:小鹿題目一：Two Sum Given an array ...

k00baa 2019-08-23 16:42 評論0 收藏0
JavaScript 數(shù)據(jù)結構與算法之美 - 冒泡排序、插入排序、選擇排序

摘要：之所以把冒泡排序選擇排序插入排序放在一起比較，是因為它們的平均時間復雜度都為。其中，冒泡排序就是原地排序算法。所以冒泡排序是穩(wěn)定的排序算法。選擇排序思路選擇排序算法的實現(xiàn)思路有點類似插入排序，也分已排序區(qū)間和未排序區(qū)間。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言算法為王。想學好前端，先練好內(nèi)功，...

canger 2019-08-26 10:15 評論0 收藏0
JavaScript 數(shù)據(jù)結構與算法之美 - 十大經(jīng)典排序算法匯總

摘要：筆者寫的數(shù)據(jù)結構與算法之美系列用的語言是，旨在入門數(shù)據(jù)結構與算法和方便以后復習。這應該是目前較為簡單的十大經(jīng)典排序算法的文章講解了吧。比如原本在的前面，而，排序之后，在的后面十大經(jīng)典排序算法冒泡排序思想冒泡排序只會操作相鄰的兩個數(shù)據(jù)。 showImg(https://segmentfault.com/img/bVbvHet); 1. 前言算法為王。想學好前端，先練好內(nèi)功，內(nèi)功不行，就...

zsy888 2019-08-26 10:27 評論0 收藏0