App下載

前端算法入門(mén)之「數(shù)據(jù)結(jié)構(gòu)」

猿友 2020-09-24 11:40:57 瀏覽數(shù) (3148)
反饋

前端算法入門(mén) -- 數(shù)據(jù)結(jié)構(gòu)

1)什么叫算法?

算法就是計(jì)算或解決問(wèn)題的步驟。

2)算法和程序有什么區(qū)別?

區(qū)別在于,程序是以計(jì)算機(jī)能夠理解的編程語(yǔ)言編寫(xiě)的,可以在計(jì)算機(jī)上運(yùn)行,而算法是以人類(lèi)能夠理解的數(shù)學(xué)方式來(lái)描述的,用于編程之前。但,算法和編程沒(méi)有具體邊界。

3)如何選擇算法?

同樣的問(wèn)題,不同的開(kāi)發(fā)者解法不同,不同的編程語(yǔ)言,寫(xiě)法不同,為算法設(shè)立評(píng)判標(biāo)準(zhǔn)的目的在于選擇最優(yōu)標(biāo)準(zhǔn)的算法。評(píng)判算法的優(yōu)劣有兩個(gè)標(biāo)準(zhǔn):一是從運(yùn)行到計(jì)算出結(jié)果需要耗費(fèi)空間的大小,另一個(gè)是從運(yùn)行到計(jì)算出結(jié)果需要花費(fèi)多少時(shí)間。分別稱(chēng)為, 空間復(fù)雜度 、 時(shí)間復(fù)雜度 。通常,復(fù)雜度越低,耗費(fèi)內(nèi)存越少,執(zhí)行越快,也更容易被人理解。一般, 最為重視的是算法的運(yùn)行時(shí)間 。

4)如何反映算法的運(yùn)行時(shí)間?

算法不同、設(shè)備不同、數(shù)據(jù)量不同都會(huì)導(dǎo)致算法時(shí)間有差異,通過(guò)理論計(jì)算出的運(yùn)行時(shí)間是一個(gè)多項(xiàng)式,而我們需要能最直觀的了解到時(shí)間隨數(shù)據(jù)量變化的關(guān)系,常常會(huì)忽略掉非重要項(xiàng),得到一個(gè)最簡(jiǎn)單的并且最能反映運(yùn)行時(shí)間趨勢(shì)的表達(dá)式,我們把:忽略掉不重要項(xiàng)、能最簡(jiǎn)表示運(yùn)行時(shí)間隨數(shù)據(jù)量變化關(guān)系寫(xiě)成O(n)的形式,其中O是大寫(xiě),表示忽略重要項(xiàng)以外的內(nèi)容,讀音同order;n表示參與算法的數(shù)據(jù)量。

數(shù)據(jù)結(jié)構(gòu)

為什么要有多種數(shù)據(jù)結(jié)構(gòu)?

根據(jù)使用目的的不同,使用不同的數(shù)據(jù)類(lèi)型,可以提供內(nèi)存空間利用率。

1)鏈表

鏈表是數(shù)據(jù)結(jié)構(gòu)之一,其數(shù)據(jù)呈線(xiàn)性排列;在內(nèi)存空間中,數(shù)據(jù)是分散存儲(chǔ)于內(nèi)存中的,每個(gè)數(shù)據(jù)都由兩部分組成,一部分是數(shù)據(jù)本身,另一部分是一個(gè)指針,它指向下一塊存儲(chǔ)空間。當(dāng)對(duì)數(shù)據(jù)進(jìn)行訪(fǎng)問(wèn)時(shí),只能順著指針指向一一往下訪(fǎng)問(wèn),直到找到或者訪(fǎng)問(wèn)到末尾,如果鏈表中的數(shù)據(jù)量是n,那么,查找到一個(gè)數(shù)據(jù),最快需要一次,最多需要查找n次;當(dāng)需要在鏈表中添加或者刪除一個(gè)數(shù)據(jù)時(shí),只需要改變其中某一個(gè)或兩個(gè)的數(shù)據(jù)指針即可,與鏈表的數(shù)據(jù)量無(wú)關(guān),是常量級(jí)的。

小結(jié):

鏈表數(shù)據(jù)是線(xiàn)性的,存儲(chǔ)空間是不連續(xù)的,訪(fǎng)問(wèn)的時(shí)間復(fù)雜度為O(n),增刪的時(shí)間復(fù)雜度為O(1)。

拓展:

循環(huán)鏈表:鏈表尾部的數(shù)據(jù)是沒(méi)有指針的,當(dāng)為尾部數(shù)據(jù)添加一個(gè)指向鏈表頭部數(shù)據(jù)的指針時(shí),鏈表指針之間就形成了環(huán)形結(jié)構(gòu),稱(chēng)為循環(huán)鏈表或環(huán)形鏈表。

雙向鏈表:當(dāng)鏈表內(nèi)部指針既可以從前一個(gè)數(shù)據(jù)指向后一個(gè)數(shù)據(jù)同時(shí)也可以從后一個(gè)元素指向前一個(gè)數(shù)據(jù)時(shí),就形成了雙向鏈表。

這里要注意:在給出定義時(shí)就說(shuō)了,數(shù)據(jù)由數(shù)據(jù)體本身和指針共同組成,當(dāng)指針增加時(shí),數(shù)據(jù)需要的存儲(chǔ)空間也會(huì)增加,就會(huì)占用更多的內(nèi)存。同時(shí),當(dāng)指針越多,增刪數(shù)據(jù)時(shí),需要改變的指針也就越復(fù)雜,需要改變指向的指針也越多。

2)數(shù)組

數(shù)組也是線(xiàn)性排列的數(shù)據(jù)結(jié)構(gòu)之一,它與鏈表不同的地方在于,數(shù)組在內(nèi)存空間的存儲(chǔ)是連續(xù)的。當(dāng)訪(fǎng)問(wèn)數(shù)組時(shí),只需要根據(jù)數(shù)組索引找到對(duì)應(yīng)位置即可,查找復(fù)雜度是常量級(jí)的,表示為O(1);而當(dāng)對(duì)數(shù)組進(jìn)行增加時(shí),如果在數(shù)組頭部增加,則需要先將數(shù)組擴(kuò)容。然后將每一個(gè)元素都依次向后移動(dòng),這個(gè)過(guò)程復(fù)雜度是O(n),而如果在數(shù)組尾部增加一個(gè)元素,復(fù)雜度變成了O(1),同理,刪除一個(gè)元素,尾部刪除時(shí)為O(1),頭部刪除時(shí)為O(n)。可以看出,相比于鏈表,數(shù)組雖然查詢(xún)方便了,但是操作復(fù)雜度卻高了。

3)棧

棧是一種線(xiàn)性數(shù)據(jù)結(jié)構(gòu),當(dāng)為棧添加一個(gè)元素時(shí),這個(gè)元素被添加到了棧的最頂端,當(dāng)取出元素時(shí),只能單向的從最前面的位置讀取,然后才能讀取后面的元素,也就是說(shuō),最后被添加的,反而是最先被讀取的,因此,棧被稱(chēng)為是后進(jìn)先出(LIFO)模式,添加和刪除數(shù)據(jù)的方式也被稱(chēng)為是入棧和出棧。由于棧具有的LIFO的特點(diǎn),它常常被用來(lái)保存最新的數(shù)據(jù)。

4)隊(duì)列

隊(duì)列也是線(xiàn)性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu),它與棧很像,都是單向的有序操作,但是,后進(jìn)先出,而隊(duì)列就像排隊(duì),先來(lái)的排在前面,后來(lái)的排在后面,屬于先進(jìn)先出(FIFO),要訪(fǎng)問(wèn)后面的元素,只能把前面的元素都訪(fǎng)問(wèn)完了,才能訪(fǎng)問(wèn)到目標(biāo)元素。添加和刪除隊(duì)列的操作也被稱(chēng)為入隊(duì)和出隊(duì)。

5)哈希表

哈希表存儲(chǔ)的是以鍵值對(duì)組合的數(shù)據(jù),一般,把鍵當(dāng)做數(shù)據(jù)的標(biāo)識(shí),而把值當(dāng)做數(shù)據(jù)的內(nèi)容。哈希表通常與哈希函數(shù)組合使用,在建立哈希表的過(guò)程中,需要使用哈希函數(shù)計(jì)算數(shù)據(jù)的哈希值,將其存在數(shù)組中,這樣在訪(fǎng)問(wèn)時(shí)就可以快速使用數(shù)組的特性訪(fǎng)問(wèn)到;如果在建立數(shù)組的時(shí)候存在多個(gè)位于同一個(gè)數(shù)組位置的值,則再次使用鏈表存儲(chǔ)相同的值。

哈希表的使用,加快了數(shù)組查詢(xún)的速度,在靈活性和高效性上有很大的優(yōu)勢(shì)。在編程中,關(guān)聯(lián)數(shù)組時(shí)常常會(huì)用到哈希表。

6)堆

堆是圖的一種,是二維的數(shù)據(jù)結(jié)構(gòu),其示意可以用二位的樹(shù)狀圖表示,子節(jié)點(diǎn)的數(shù)據(jù)值總比父節(jié)點(diǎn)大。在堆中,頂端的數(shù)據(jù)始終是最小的,所以無(wú)論多少數(shù)據(jù)量,取出最小值的復(fù)雜度始終都是O(1)。另外,由于取出數(shù)據(jù)后需要將最后的數(shù)據(jù)移動(dòng)到最頂端,然后一邊比較它與子節(jié)點(diǎn)數(shù)據(jù)的大小,一邊往下移動(dòng),所以,取出數(shù)據(jù)需要的運(yùn)行時(shí)間和樹(shù)的高度成正比,假設(shè)數(shù)據(jù)量為n,根據(jù)堆的形狀特點(diǎn)可知,樹(shù)的高度為log2n,那么重構(gòu)樹(shù)的復(fù)雜度就是O(logn).添加數(shù)據(jù)也一樣,在堆的最后添加數(shù)據(jù),數(shù)據(jù)一邊比較它與父節(jié)點(diǎn)的大小,一邊往上移動(dòng),知道滿(mǎn)足堆的條件為止。

如果需要頻繁的從數(shù)據(jù)中取出最小值,那么,堆,是一種很好的選擇。

7)二叉查找樹(shù)

二叉查找樹(shù)也叫作二叉搜索樹(shù),或二叉排序樹(shù)。是二維的圖結(jié)構(gòu)的一種。它的特點(diǎn)是:每個(gè)節(jié)點(diǎn)最多有兩個(gè)節(jié)點(diǎn),分別稱(chēng)為左子樹(shù)和右子樹(shù),每一個(gè)節(jié)點(diǎn)上的值均大于其左子樹(shù)上的值,每個(gè)節(jié)點(diǎn)上的值均小于其右子樹(shù)上的值。

根據(jù)這兩個(gè)特點(diǎn)可知: 二叉查找樹(shù)查找最小值要往左下末端找,查找最大值要往右下末端找 。

數(shù)據(jù)結(jié)構(gòu)到底選哪種要根據(jù)使用目的來(lái)確定,前端常用的為以上7種。

以上就是W3Cschool編程獅關(guān)于前端算法入門(mén)之「數(shù)據(jù)結(jié)構(gòu)」的相關(guān)介紹了,希望對(duì)大家有所幫助。

文章來(lái)源:www.toutiao.com/i6858491700608762380/

0 人點(diǎn)贊