什么是 DSA？

DSA（Data Structures and Algorithms）。

在計(jì)算機(jī)科學(xué)的背景下，術(shù)語(yǔ) DSA 代表 數(shù)據(jù)結(jié)構(gòu)和算法。

數(shù)據(jù)結(jié)構(gòu)與算法簡(jiǎn)介（DSA）

什么是數(shù)據(jù)結(jié)構(gòu)？

數(shù)據(jù)結(jié)構(gòu)被定義為在我們的設(shè)備中存儲(chǔ)和組織數(shù)據(jù)以高效且有效地使用數(shù)據(jù)的特定方式。使用數(shù)據(jù)結(jié)構(gòu)背后的主要思想是最小化時(shí)間和空間復(fù)雜性。高效的數(shù)據(jù)結(jié)構(gòu)占用最少的內(nèi)存空間并需要最少的時(shí)間來(lái)執(zhí)行數(shù)據(jù)。

什么是算法？

算法被定義為一個(gè)過(guò)程或一組定義明確的指令，通常用于解決一組特定的問(wèn)題或執(zhí)行特定類型的計(jì)算。簡(jiǎn)單來(lái)說(shuō)，就是為了執(zhí)行任務(wù)而按步驟的方式進(jìn)行的一組操作。

認(rèn)識(shí)DSA

時(shí)間和空間復(fù)雜性

這是一個(gè)有趣且重要的話題。使用 DSA 的主要?jiǎng)訖C(jī)是有效且高效地解決問(wèn)題。如何判斷自己編寫(xiě)的程序是否高效？這是通過(guò)復(fù)雜性來(lái)衡量的。復(fù)雜性有兩種類型：

• 時(shí)間復(fù)雜度：時(shí)間復(fù)雜度用于衡量執(zhí)行代碼所需的時(shí)間量。
• 空間復(fù)雜度：空間復(fù)雜度是指成功執(zhí)行代碼功能所需的空間量。

上述兩種復(fù)雜性都是根據(jù)輸入?yún)?shù)來(lái)測(cè)量的。但這里出現(xiàn)了一個(gè)問(wèn)題。執(zhí)行代碼所需的時(shí)間取決于幾個(gè)因素，例如：

• 程序中執(zhí)行的操作數(shù)量。
• 以及設(shè)備的速度。
• 在平臺(tái)執(zhí)行時(shí)數(shù)據(jù)傳輸?shù)乃俣取?/span>

以下3種漸近符號(hào)主要用于表示算法的時(shí)間復(fù)雜度：

• Big-O 表示法 (Ο) – Big-O 表示法專門(mén)描述了最壞的情況。
• Omega 表示法 (Ω) – Omega(Ω) 表示法專門(mén)描述了最佳情況。
• Theta 表示法 (θ) – 該表示法表示算法的平均復(fù)雜度。

算法的增長(zhǎng)率

PS：橫坐標(biāo)：輸入數(shù)據(jù)的大小；縱坐標(biāo)：執(zhí)行的完成時(shí)間。

代碼分析中最常用的表示法是Big O 表示法，它給出了代碼運(yùn)行時(shí)間的上限（或輸入大小方面使用的內(nèi)存量）。

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

數(shù)組（Array）

最基本但重要的數(shù)據(jù)結(jié)構(gòu)是數(shù)組。它是一種線性數(shù)據(jù)結(jié)構(gòu)。數(shù)組是同類數(shù)據(jù)類型的集合，其中元素被分配連續(xù)的內(nèi)存。由于內(nèi)存的連續(xù)分配，數(shù)組的任何元素都可以在恒定時(shí)間內(nèi)訪問(wèn)。每個(gè)數(shù)組元素都有一個(gè)對(duì)應(yīng)的索引號(hào)。

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

鏈表（Linked Lists）

和上面的數(shù)據(jù)結(jié)構(gòu)一樣，鏈表也是一種線性數(shù)據(jù)結(jié)構(gòu)。但Linked List在配置上與Array不同。它沒(méi)有分配到連續(xù)的內(nèi)存位置。相反，鏈表的每個(gè)節(jié)點(diǎn)都被分配到一些隨機(jī)內(nèi)存空間，并且前一個(gè)節(jié)點(diǎn)維護(hù)一個(gè)指向該節(jié)點(diǎn)的指針。因此任何節(jié)點(diǎn)都不可能直接訪問(wèn)內(nèi)存，而且它也是動(dòng)態(tài)的，即鏈表的大小可以隨時(shí)調(diào)整。

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

鏈表的不同實(shí)現(xiàn)：

• 單向鏈表– 鏈表中的每個(gè)節(jié)點(diǎn)僅指向其下一個(gè)節(jié)點(diǎn)。
• 循環(huán)鏈表——這是最后一個(gè)節(jié)點(diǎn)指向鏈表頭的鏈表類型。
• 雙向鏈表——在這種情況下，鏈表的每個(gè)節(jié)點(diǎn)都保存兩個(gè)指針，一個(gè)指向下一個(gè)節(jié)點(diǎn)，另一個(gè)指向前一個(gè)節(jié)點(diǎn)。

堆棧（Stack）

堆棧是一種線性數(shù)據(jù)結(jié)構(gòu)，遵循特定的操作執(zhí)行順序。順序可以是LIFO（后進(jìn)先出）或 FILO（先進(jìn)后出）。

Stack之所以被認(rèn)為是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，是因?yàn)樗鶕?jù)Stack數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)和特點(diǎn)，使用了其他數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)，比如數(shù)組、鏈表等。

隊(duì)列（Queue）

Stack類似但特性不同的數(shù)據(jù)結(jié)構(gòu)是Queue。

隊(duì)列是一種線性結(jié)構(gòu)，其各個(gè)操作遵循先進(jìn)先出 (FIFO)方法。

隊(duì)列可以有不同的類型，例如：

• 循環(huán)隊(duì)列——在循環(huán)隊(duì)列中，最后一個(gè)元素連接到隊(duì)列的第一個(gè)元素
• 雙端隊(duì)列（或稱為雙端隊(duì)列） ——雙端隊(duì)列是一種特殊類型的隊(duì)列，可以從隊(duì)列的兩端執(zhí)行操作。
• 優(yōu)先級(jí)隊(duì)列——這是一種特殊類型的隊(duì)列，其中元素按照其優(yōu)先級(jí)排列。低優(yōu)先級(jí)元素在高優(yōu)先級(jí)元素之后出列。

堆（Heap）

堆是一種特殊的基于樹(shù)的數(shù)據(jù)結(jié)構(gòu)，其中樹(shù)是完全二叉樹(shù)。

堆的類型：

一般來(lái)說(shuō)，堆有兩種類型。

大頂堆：

在這個(gè)堆中，根節(jié)點(diǎn)的值必須是其所有子節(jié)點(diǎn)中最大的，并且其左右子樹(shù)也必須執(zhí)行相同的操作。

小頂堆：

在這個(gè)堆中，根節(jié)點(diǎn)的值必須是其所有子節(jié)點(diǎn)中最小的，并且其左右子樹(shù)也必須執(zhí)行相同的操作。

哈希（Hash）

散列是指使用稱為散列函數(shù)的數(shù)學(xué)公式從可變大小的輸入生成固定大小的輸出的過(guò)程。該技術(shù)確定數(shù)據(jù)結(jié)構(gòu)中項(xiàng)目存儲(chǔ)的索引或位置。

樹(shù)（Tree）

樹(shù)數(shù)據(jù)結(jié)構(gòu)類似于我們?cè)谧匀唤缰锌吹降臉?shù)，但它是顛倒的。它也有根和葉。根是樹(shù)的第一個(gè)節(jié)點(diǎn)，葉子是最底層的節(jié)點(diǎn)。樹(shù)的特點(diǎn)是從它的任何一個(gè)節(jié)點(diǎn)到任何其他節(jié)點(diǎn)只有一條路徑。

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

樹(shù)有多種不同的類型和變種，常見(jiàn)的樹(shù)包括：

• 二叉樹(shù)（Binary Tree）：每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)，分別稱為左子節(jié)點(diǎn)和右子節(jié)點(diǎn)。
• 二叉搜索樹(shù)（Binary Search Tree）：二叉樹(shù)的一種特殊形式，其中左子節(jié)點(diǎn)的值小于等于父節(jié)點(diǎn)的值，右子節(jié)點(diǎn)的值大于等于父節(jié)點(diǎn)的值，便于進(jìn)行快速的搜索和插入操作。
• 平衡樹(shù)（Balanced Tree）：樹(shù)的節(jié)點(diǎn)在高度上保持平衡，以確保樹(shù)的操作具有良好的性能。常見(jiàn)的平衡樹(shù)包括AVL樹(shù)、紅黑樹(shù)等。
• 堆（Heap）：一種特殊的樹(shù)結(jié)構(gòu)，用于高效地找到最大值或最小值。常見(jiàn)的堆包括最大堆和最小堆。
• B樹(shù)（B-tree）：一種多路搜索樹(shù)，常用于數(shù)據(jù)庫(kù)和文件系統(tǒng)等存儲(chǔ)系統(tǒng)，具有高度的平衡性和高效的查找操作。

圖（Graph）

它類似于Tree數(shù)據(jù)結(jié)構(gòu)，不同之處在于沒(méi)有特定的根或葉節(jié)點(diǎn)，并且可以按任意順序遍歷。

圖是一種非線性數(shù)據(jù)結(jié)構(gòu)，由一組有限的頂點(diǎn)（或節(jié)點(diǎn)）和一組連接一對(duì)節(jié)點(diǎn)的邊組成 。

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

每條邊都顯示一對(duì)節(jié)點(diǎn)之間的連接。這種數(shù)據(jù)結(jié)構(gòu)有助于解決許多現(xiàn)實(shí)生活中的問(wèn)題。根據(jù)邊和節(jié)點(diǎn)的方向，有各種類型的圖。

以下是一些必須了解的圖概念：

• 圖的類型：根據(jù)節(jié)點(diǎn)的連通性或權(quán)重，有不同類型的圖。
• BFS 和 DFS ： 這些是遍歷圖的算法
• 圖中的循環(huán)：循環(huán)是一系列連接，我們將在循環(huán)中移動(dòng)這些連接。
• 圖中的拓?fù)渑判?/span>
• 圖中的最小生成樹(shù)

算法

搜索算法

搜索算法用于查找數(shù)組、字符串、鏈表或其他數(shù)據(jù)結(jié)構(gòu)中的特定元素。

最常見(jiàn)的搜索算法是：

• 線性搜索- 在此搜索算法中，我們從一端到另一端迭代地檢查元素。
• 二分搜索——在這種類型的搜索算法中，我們將數(shù)據(jù)結(jié)構(gòu)分成兩個(gè)相等的部分，并嘗試決定需要在哪一半中查找元素。
• 三元搜索——在這種情況下，數(shù)組被分為三個(gè)部分，根據(jù)分區(qū)位置的值，我們決定需要在哪個(gè)段中查找所需元素。

除此之外，還有其他搜索算法，例如

• 跳轉(zhuǎn)搜索
• 插值搜索
• 指數(shù)搜索

排序算法

通常我們需要根據(jù)特定條件對(duì)數(shù)據(jù)進(jìn)行排列或排序。排序算法就是在這些情況下使用的算法。根據(jù)條件，我們可以對(duì)一組同質(zhì)數(shù)據(jù)進(jìn)行排序，就像按升序或降序?qū)?shù)組進(jìn)行排序一樣。

排序算法用于根據(jù)元素上的比較運(yùn)算符重新排列給定的數(shù)組或列表元素。比較運(yùn)算符用于決定相應(yīng)數(shù)據(jù)結(jié)構(gòu)中元素的新順序。

顯示排序的示例

有許多不同類型的排序算法。一些廣泛使用的算法是：

• 快速排序
• 歸并排序
• 堆排序
• 冒泡排序
• 插入排序
• 選擇排序
• 樹(shù)排序
• 等等

排序算法的復(fù)雜性

分治算法

顧名思義，它將問(wèn)題分解為多個(gè)部分，然后解決每個(gè)部分，然后再次合并已解決的子任務(wù)以解決實(shí)際問(wèn)題。

分而治之是一種算法范式。典型的分而治之算法使用以下三個(gè)步驟解決問(wèn)題。

• 分解（Divide）：將給定問(wèn)題分解為相同類型的子問(wèn)題。
• 解決（Conquer）：遞歸地解決這些子問(wèn)題。
• 合并（Combine）：將子問(wèn)題合并為原始問(wèn)題的解決方案。

這是前面提到的歸并排序和快速排序這兩種排序算法中提到的主要技術(shù)。

貪心算法

顧名思義，該算法一次構(gòu)建一個(gè)解決方案，并選擇下一個(gè)提供最明顯和直接好處的解決方案，即當(dāng)時(shí)的最佳選擇。因此，選擇局部最優(yōu)也導(dǎo)致全局解決方案的問(wèn)題最適合貪婪。

例如，考慮分?jǐn)?shù)背包問(wèn)題。局部最優(yōu)策略是選擇具有最大價(jià)值與重量比的項(xiàng)目。這種策略還可以產(chǎn)生全局最優(yōu)解決方案，因?yàn)槲覀兛梢垣@取某個(gè)項(xiàng)目的一部分。

回溯算法

回溯算法源自遞歸算法，如果遞歸解決方案失敗，則可以選擇恢復(fù)，即如果解決方案失敗，程序?qū)⒆匪莸绞〉臅r(shí)刻并構(gòu)建另一個(gè)解決方案。所以基本上它會(huì)嘗試所有可能的解決方案并找到正確的解決方案。

回溯是一種遞歸解決問(wèn)題的算法技術(shù)，通過(guò)嘗試逐步構(gòu)建解決方案，一次一個(gè)部分，刪除那些在任何時(shí)間點(diǎn)都無(wú)法滿足問(wèn)題約束的解決方案

動(dòng)態(tài)規(guī)劃

動(dòng)態(tài)編程主要是對(duì)普通遞歸的優(yōu)化。無(wú)論何時(shí)我們看到重復(fù)調(diào)用相同輸入的遞歸解決方案，我們都可以使用動(dòng)態(tài)編程對(duì)其進(jìn)行優(yōu)化。

動(dòng)態(tài)規(guī)劃算法的主要思想是利用先前計(jì)算的結(jié)果來(lái)避免同一子任務(wù)的重復(fù)計(jì)算，從而有助于降低時(shí)間復(fù)雜度。

動(dòng)態(tài)規(guī)劃

圖算法

圖算法用于解決將圖表示為網(wǎng)絡(luò)的問(wèn)題，例如航空公司航班、互聯(lián)網(wǎng)如何連接或 社交軟件里人之間親密度。它們?cè)贜LP和機(jī)器學(xué)習(xí)中也很流行，用于形成網(wǎng)絡(luò)。

一些頂級(jí)的圖形算法包括：

• 實(shí)現(xiàn)廣度優(yōu)先遍歷
• 實(shí)現(xiàn)深度優(yōu)先遍歷
• 計(jì)算圖級(jí)別中的節(jié)點(diǎn)數(shù)
• 查找兩個(gè)節(jié)點(diǎn)之間的所有路徑
• 查找圖的所有連通分量
• 迪杰斯特拉算法（Dijkstra） 在圖數(shù)據(jù)中查找最短路徑
• 移除邊緣

總結(jié)

本篇是從理論和概念上對(duì)數(shù)據(jù)結(jié)構(gòu)與算法的一些簡(jiǎn)單介紹，后面會(huì)詳細(xì)解釋數(shù)據(jù)結(jié)構(gòu)和算法。