摘要：數(shù)據(jù)結(jié)構(gòu)程序數(shù)據(jù)結(jié)構(gòu)算法數(shù)據(jù)結(jié)構(gòu)基本概念數(shù)據(jù)的邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的關(guān)系的數(shù)據(jù)元素集合的表示。這兩部分信息組成數(shù)據(jù)元素的存儲映象，稱為結(jié)點(diǎn)。

本文涉及更多的是概念，代碼部分請參考之前寫過的 2 篇博客

基于 Javascript 的排序算法

基于 javascript 的基本數(shù)據(jù)結(jié)構(gòu)和查找算法

本文主要是基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)和算法概念，可能部分地方會涉及更高級的算法和算法，具體內(nèi)容以后會多帶帶寫的。此外一些性質(zhì)還會不斷補(bǔ)充，也希望可以得到您的指點(diǎn)，謝謝。

程序 = 數(shù)據(jù)結(jié)構(gòu) + 算法

數(shù)據(jù)的邏輯結(jié)構(gòu)：反映數(shù)據(jù)元素之間的關(guān)系的數(shù)據(jù)元素集合的表示。數(shù)據(jù)的邏輯結(jié)構(gòu)包括集合、線形結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)四種。

數(shù)據(jù)的存儲結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲空間種的存放形式稱為數(shù)據(jù)的存儲結(jié)構(gòu)。常用的存儲結(jié)構(gòu)有順序、鏈接、索引等存儲結(jié)構(gòu)。

在數(shù)據(jù)結(jié)構(gòu)中，沒有前件的結(jié)點(diǎn)稱為根結(jié)點(diǎn)，沒有后件的結(jié)點(diǎn)成為終端結(jié)點(diǎn)

數(shù)據(jù)結(jié)構(gòu)的基本操作

插入和刪除是對數(shù)據(jù)結(jié)構(gòu)的兩種基本操作。此外還有查找、分類、合并、分解、復(fù)制和修改等。

線性結(jié)構(gòu)和非線性結(jié)構(gòu)

根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。

線性結(jié)構(gòu)：有且只有一個(gè)根結(jié)點(diǎn)；每個(gè)結(jié)點(diǎn)最多有一個(gè)前件，最多只有一個(gè)后件。

非線性結(jié)構(gòu)： 如果一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，稱之為非線性結(jié)構(gòu)。

本文涉及一下內(nèi)容：

四種線性結(jié)構(gòu)的存儲結(jié)構(gòu)：順序表、鏈表、索引、散列

兩種常見的線性邏輯結(jié)構(gòu)：隊(duì)列、棧

非線性邏輯結(jié)構(gòu)：循環(huán)隊(duì)列、雙向隊(duì)列、雙向循環(huán)隊(duì)列、樹、圖

順序表是線性表的順序存儲結(jié)構(gòu)，指的是用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素。
順序表具備如下兩個(gè)基本特征：

順序表中的所有元素所占的存儲空間是連續(xù)的；

順序表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。

假設(shè)順序表的每個(gè)元素需占用 $K$ 個(gè)存儲單元，并以所占的第一個(gè)單元的存儲地址作為數(shù)據(jù)元素的存儲位置。則順序表中第 $i+1$ 個(gè)數(shù)據(jù)元素的存儲位置 $LOC(a_i+1)$ 和第 $i$ 個(gè)數(shù)據(jù)元素的存儲位置 $LOC(a_i)$ 之間滿足下列關(guān)系為:

$LOC(a_{i+1}) = LOC(a_i)+K$
$LOC(a_i) = LOC(a_1)+(i-1)*K$

其中，$LOC(a_1)$是順序表的第一個(gè)數(shù)據(jù)元素 $a_1$ 的存儲位置，通常稱做順序表的起始位置或基地址。順序存儲結(jié)構(gòu)也稱隨機(jī)存取結(jié)構(gòu)。

順序表常見操作(括號中為算法平均時(shí)間復(fù)雜度，沒有寫明的具體復(fù)雜度依賴不同算法和運(yùn)算規(guī)則)：

插入($O(n)$)、刪除($O(n)$)、查找、排序、分解、合并、復(fù)制($O(n)$)、逆轉(zhuǎn)($O(n)$)

鏈表指線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。一組任意的存儲單元存儲線性表的數(shù)據(jù)元素，因此，為了表示每個(gè)數(shù)據(jù)元素 $a_i$ 與其直接后繼數(shù)據(jù)元素 $a_{i+1}$ 之間的邏輯關(guān)系，對數(shù)據(jù)元素 $a_i$ 來說，除了存儲其本身的信息(數(shù)據(jù)域)之外，還需存儲一個(gè)變量指示其直接后繼的信息(指針域)。這兩部分信息組成數(shù)據(jù)元素 $a_i$ 的存儲映象，稱為結(jié)點(diǎn)。$N$ 個(gè)結(jié)點(diǎn)鏈結(jié)成一個(gè)鏈表。該鏈表就是傳統(tǒng)的單向鏈表。

有時(shí)，我們在單鏈表的第一個(gè)結(jié)點(diǎn)之前附設(shè)一個(gè)結(jié)點(diǎn)，稱之為頭結(jié)點(diǎn)，它指向表中第一個(gè)結(jié)點(diǎn)。頭結(jié)點(diǎn)的數(shù)據(jù)域可 以不存儲任何信息，也可存儲如線性表的長度等類的附加信息，頭結(jié)點(diǎn)的指針域存儲指向第一個(gè)結(jié)點(diǎn)的指針。在單鏈表中，取得第 I 個(gè)數(shù)據(jù)元素必須從頭指針出發(fā)尋找，因此，鏈表是非隨機(jī)存取的存儲結(jié)構(gòu)。

以上提到的鏈表指針域只包括一個(gè)指針，指向下一個(gè)數(shù)據(jù)的地址，如果我們將鏈表最后一個(gè)結(jié)點(diǎn)指針域的指針指向鏈表的頭結(jié)點(diǎn)地址，就構(gòu)成了一個(gè)環(huán)狀的存儲結(jié)構(gòu)，我們稱作循環(huán)鏈表。

當(dāng)然我們可以給每個(gè)結(jié)點(diǎn)的指針域再添加一個(gè)指針，使其指向前一個(gè)數(shù)據(jù)結(jié)點(diǎn)的地址，這樣就構(gòu)成了雙向鏈表，而將頭結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)指向尾結(jié)點(diǎn)，同時(shí)將尾結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)指向頭結(jié)點(diǎn)就構(gòu)成了雙向循環(huán)鏈表。

如果鏈表的尾結(jié)點(diǎn)的指針域指向了該鏈表之前的任意一個(gè)結(jié)點(diǎn)，我們稱該鏈表為有環(huán)鏈表。環(huán)形鏈表就是其中一個(gè)特例

順序表常見操作(括號中為算法平均時(shí)間復(fù)雜度，沒有寫明的具體復(fù)雜度依賴不同算法和運(yùn)算規(guī)則)：

插入($O(n)$)、刪除($O(n)$)、查找、排序、分解、合并、復(fù)制($O(n)$)、逆轉(zhuǎn)($O(n)$)

索引存儲除建立存儲結(jié)點(diǎn)信息外，還建立附加的索引表來標(biāo)識結(jié)點(diǎn)的地址。索引表由若干索引項(xiàng)組成。

對于索引的理解最好的例子就是《新華字典》，它建立的2套索引表(拼音、部首)。字典的正文就是從“啊”到“做”的每個(gè)字的解釋，有上千頁，就是是數(shù)據(jù)。而前面的拼音/部首就是索引表，索引表告訴你某個(gè)讀音/部首在第幾頁，這就好比是指向數(shù)據(jù)地址的指針。而索引表可以有一級的也可以是多級的，比如字典中的部首索引就是兩級的。

索引存儲結(jié)構(gòu)是用結(jié)點(diǎn)的索引號來確定結(jié)點(diǎn)存儲地址，其優(yōu)點(diǎn)是檢索速度快，缺點(diǎn)是增加了附加的索引表,會占用較多的存儲空間。

散列存儲，又稱哈希(hash)存儲，是一種力圖將數(shù)據(jù)元素的存儲位置(預(yù)留連續(xù)存儲區(qū)域)與關(guān)鍵碼之間建立確定對應(yīng)關(guān)系的查找技術(shù)。散列法存儲的基本思想是由結(jié)點(diǎn)的關(guān)鍵碼值決定結(jié)點(diǎn)的存儲地址。散列技術(shù)除了可以用于存儲外，還可以用于查找。

散列以數(shù)據(jù)中每個(gè)元素的關(guān)鍵字 $K$ 為自變量，通過散列函數(shù) $H(k)$ 計(jì)算出函數(shù)值，以該函數(shù)值作為一塊連續(xù)存儲空間的的單元地址，將該元素存儲到函數(shù)值對應(yīng)的單元中。由于該函數(shù)值唯一，所以查找時(shí)間復(fù)雜度為 $O(1)$

線性表滿足以下特征:

有且只有一個(gè)根結(jié)點(diǎn) $a_1$,它無前件；

有且只有一個(gè)終端結(jié)點(diǎn) $a_n$，它無后件；

除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外，其他所有結(jié)點(diǎn)有且只有一個(gè)前件，也有且只有一個(gè)后件。線性表中結(jié)點(diǎn)的個(gè)數(shù) $n$ 稱 為線性表的長度。當(dāng) $n=0$ 時(shí)稱為空表。

棧實(shí)際上也是一個(gè)線性表，只不過是一種特殊的線性表。棧是只能在表的一端進(jìn)行插入和刪除運(yùn)算的線性表，通常稱插入、刪除這一端為棧頂(TOP)，另一端為棧底(BOTTOM)。當(dāng)表中沒有元素時(shí)稱為?？?。 棧頂元素總是后被插入(入棧)的元素，從而也是最先被移除(出棧)的元素；棧底元素總是最先被插入的元素，從而也是最后才能被移除的元素。所以棧是個(gè) 后進(jìn)先出(LIFO) 的數(shù)據(jù)結(jié)構(gòu)

棧的基本運(yùn)算有三種：入棧、出棧與讀棧頂，時(shí)間復(fù)雜度都是$O(1)$

隊(duì)列是只允許在一端刪除，在另一端插入的順序表，允許刪除的一端叫做隊(duì)頭，用對頭指針 $front$ 指向?qū)︻^元素的下一個(gè)元素，允許插入的一端叫做隊(duì)尾，用隊(duì)尾指針 $rear$ 指向隊(duì)列中的隊(duì)尾元素，因此，從排頭指針 $front$ 指向的下一個(gè)位置直到隊(duì)尾指針 $rear$ 指向的位置之間所有的元素均為隊(duì)列中的元素。

隊(duì)列的修改是 先進(jìn)先出(FIFO) 。往隊(duì)尾插入一個(gè)元素稱為入隊(duì)運(yùn)算。從對頭刪除一個(gè)元素稱為退隊(duì)運(yùn)算。

隊(duì)列主要有兩種基本運(yùn)算：入隊(duì)運(yùn)算和退隊(duì)運(yùn)算，復(fù)雜度都是$O(1)$

在實(shí)際應(yīng)用中，隊(duì)列的順序存儲結(jié)構(gòu)一般采用循環(huán)隊(duì)列的形式。所謂循環(huán)隊(duì)列，就是將隊(duì)列存儲空間的最后一個(gè) 位置繞到第一個(gè)位置，形成邏輯上的環(huán)狀空間。在實(shí)際使用循環(huán)隊(duì)列時(shí)，為了能區(qū)分隊(duì)滿還是隊(duì)列空，通常需要增加一個(gè)標(biāo)志 $S$。

循環(huán)隊(duì)列主要有兩種基本運(yùn)算：入隊(duì)運(yùn)算和退隊(duì)運(yùn)算，復(fù)雜度都是$O(1)$

入隊(duì)運(yùn)算

指在循環(huán)隊(duì)列的隊(duì)尾加入一個(gè)新元素，首先 $rear=rear+1$, 當(dāng) $rear=m+1$ 時(shí)，置 $rear=1$,然后將新元素插入到隊(duì)尾指針 指向的位置。當(dāng) $S=1, rear=front$，說明隊(duì)列已滿，不能進(jìn)行入隊(duì)運(yùn)算，稱為“上溢”。

退隊(duì)運(yùn)算

指在循環(huán)隊(duì)列的排頭位置退出一個(gè)元素并賦給指定的變量。首先 $front=front+1$, 并當(dāng) $front=m+1$ 時(shí)，置 $front=1$, 然后 將排頭指針指向的元素賦給指定的變量。當(dāng)循環(huán)隊(duì)列為空 $S=0$，不能進(jìn)行退隊(duì)運(yùn)算，這種情況成為“下溢”。

樹是一種簡單的非線性結(jié)構(gòu)。樹型結(jié)構(gòu)具有以下特點(diǎn)：

每個(gè)結(jié)點(diǎn)只有一個(gè)前件，稱為父結(jié)點(diǎn)，沒有前件的結(jié)點(diǎn)只有一個(gè)，稱為樹的根結(jié)點(diǎn)。

每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件結(jié)點(diǎn)，稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。沒有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)

一個(gè)結(jié)點(diǎn)所擁有的后件個(gè)數(shù)稱為結(jié)點(diǎn)的度

樹的最大層次稱為樹的深度。

二叉樹是一種樹型結(jié)構(gòu)，通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，滿足以下特性：

它的特點(diǎn)是每個(gè)結(jié)點(diǎn)至多只有二棵子樹(即二叉樹中不存在度大于 2 的結(jié)點(diǎn))；

二叉樹的子樹有左右之分，其次序不能任意顛倒。

二叉樹的基本性質(zhì)

在二叉樹的第 $i$ 層上至多有 $2i-1$ 個(gè)結(jié)點(diǎn)

深度為 $k$ 的二叉樹至多有 $2k-1$ 個(gè)結(jié)點(diǎn)($k geq 1$)

在任意一個(gè)二叉樹中，度為 0 的結(jié)點(diǎn)總是比度為 2 的結(jié)點(diǎn)多一個(gè)

具有 $N$ 個(gè)結(jié)點(diǎn)的二叉樹，其深度至少為 $lfloor log_2 N floor+1$

霍夫曼樹的帶權(quán)路徑長度 $len = 2n+1$; $n$ 為所以葉子權(quán)重和。

二叉樹的遍歷

就是遵從某種次序，訪問二叉樹中的所有結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)僅被訪問一次。分為以下幾種：

前序遍歷(DLR): 首先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹。

中序遍歷(LDR): 首先遍歷左子樹，然后根結(jié)點(diǎn)，最后右子樹

后序遍歷(LRD): 首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點(diǎn)。

此外圖的遍歷也可以用在樹上，包括：

廣度優(yōu)先遍歷(層序遍歷): 從根結(jié)點(diǎn)開開始逐層向下，從左到右遍歷。

深度優(yōu)先遍歷: 從根結(jié)點(diǎn)出發(fā)沿左子樹遍歷到葉子結(jié)點(diǎn)再逐層向上向遍歷右子樹。

除此之外還有很多有特點(diǎn)的特殊二叉樹：

滿二叉樹：除最后一層以外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。

在滿二叉樹的第 $K$ 層上有 $2^{K-1}$ 個(gè)結(jié)點(diǎn)，且深度為 $M$ 的滿二叉樹有 $2M-1$ 個(gè)結(jié)點(diǎn)

完全二叉樹：除最后一層以外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值；在最后一層上只缺少右邊的若干結(jié)點(diǎn)。

具有 $N$ 個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 $lfloor log_2 N 
floor+1$
完全二叉樹總結(jié)點(diǎn)數(shù)為 $N$，則葉子結(jié)點(diǎn)數(shù)為$lceil N/2 
ceil$

最常見的完全二叉樹就是 堆 了。堆滿足以下條件

堆中某個(gè)結(jié)點(diǎn)的值總是不大于或不小于其父結(jié)點(diǎn)的值

堆總是一棵完全二叉樹

將根結(jié)點(diǎn)最大的堆叫做 最大堆 或 大根堆 ，根結(jié)點(diǎn)最小的堆叫做 最小堆 或 小根堆 。

堆具有以下基本操作：

插入: 向堆中插入一個(gè)新元素

獲取: 獲取當(dāng)前堆頂元素的值

刪除: 刪除堆頂元素

包含: 判斷堆中是否存在某個(gè)元素

常用的哈希函數(shù)

直接尋址法: $H(k)$ 是一個(gè)線性函數(shù)，如果該位置已經(jīng)有值就向下尋找到第一個(gè)空的地方作為散列地址

平方取中法: 取 $k$ 平方以后值的中間幾位作為散列地址

數(shù)字分析法: 對于比較規(guī)律的 $k$ 值，找出其差異較大的部分作為散列地址

折疊法: 將 $k$ 分成很多部分，然后做模二和作為散列地址

留余數(shù)法: $H(k)=k % p, p leq m$，其中 $p$ 為素?cái)?shù)，$m$ 為表的長度

隨機(jī)數(shù)法: 取鍵字的隨機(jī)值作為散列地址，關(guān)鍵字長度時(shí)使用

實(shí)現(xiàn)映射的函數(shù)是哈希函數(shù)，簡單的 hash 可能會發(fā)生碰撞(不同輸入得到相同輸出)，為了防止碰撞，考慮以下方法：

鏈地址法(拉鏈法): 當(dāng)發(fā)生碰撞時(shí)，將發(fā)生碰撞的數(shù)據(jù)元素連接到同一個(gè)單鏈表中，而新元素插入到鏈表的前端

線性探針法: 線性探針法地址增量 $d in D_1 = {1,2,3, ... , m-1}$, $i$ 為探測次數(shù)，$m$ 為表的長度，該方法遇到?jīng)_突地址會依次探測下一個(gè)地址($d = d_i + 1$)直到有空的地址，若找不到空地址，則溢出。

平均查找長度

線性探針法平均長度推算(其中 $m$ 為表中數(shù)據(jù)長度，$n$ 為表長度)：

$ASL_s=frac{sum_{i=1}^m d_i}{m}$，查找成功
$ASL_u=frac{sum_{i=1}^n d_i}{n}$，查找不成功

注：線性探針法查找成功時(shí) $d_i$ 為每次放入元素時(shí)的地址增量，不成功時(shí) $d_i$ 為在表長度內(nèi)依次查找每個(gè)元素到下一個(gè)空地址的地址增量(索引在表長度內(nèi)循環(huán))

鏈地址法平均長度推算(其中 $k$ 為最長鏈長度，其中 $m$ 為表中數(shù)據(jù)長度，$n$ 為表長度)：

$ASL_s=frac{sum_{i=1}^k ({當(dāng)前級指針數(shù)量} 	imes {當(dāng)前級數(shù)})}{m}$，查找成功
$ASL_u=frac{sum_{i=1}^n {當(dāng)前個(gè)位置鏈長度}}{n}$，查找不成功

哈希表相關(guān)特性

線性探針法容易“聚集”，影響查找效率，而鏈地址法不會

鏈地址法適應(yīng)表長不確定情況

$裝填因子(alpha)=frac{哈希表中的記錄數(shù)}{哈希表的長度}$

圖有兩種定義：

二元組的定義：圖 $G$ 是一個(gè)有序二元組 $(V,E)$，其中 $V$ 稱為頂集(Vertices Set)，$E$ 稱為邊集(Edges set)，$E$ 與 $V$ 不相交。它們亦可寫成 $V(G)$ 和 $E(G)$ 。$E$ 的元素都是二元組，用 $(x,y)$ 表示，其中 $x,y in V$

三元組的定義: 圖 $G$ 是指一個(gè)三元組$(V,E,I)$，其中 $V$ 稱為頂集，$E$ 稱為邊集，$E$ 與 $V$ 不相交；$I$ 稱為關(guān)聯(lián)函數(shù)，$I$ 將 $E$ 中的每一個(gè)元素映射到$V imes V$。如果 $e$ 被映射到 $(u,v)$，那么稱邊 $e$ 連接頂點(diǎn) $u,v$，而 $u,v$ 則稱作 $e$ 的端點(diǎn)，$u,v$ 此時(shí)關(guān)于 $e$ 相鄰。同時(shí)，若兩條邊 $i,j$ 有一個(gè)公共頂點(diǎn) $u$，則稱 $i,j$ 關(guān)于 $u$ 相鄰。

圖的分類

圖有不同的分類規(guī)則，具體如下：

分類1

有向圖: 如果圖中頂點(diǎn)之間關(guān)系不僅僅是連通與不連通，而且區(qū)分兩邊的頂點(diǎn)的出入(存在出邊和入邊)，則為有向圖。

無向圖: 如果圖中頂點(diǎn)之間關(guān)系僅僅是連通與不連通，而不區(qū)分兩邊頂點(diǎn)的出入(不存在出邊和入邊)，則為無向圖。

單圖

分類2

有環(huán)圖: 單向遍歷回可以到已遍歷的點(diǎn)，比如有環(huán)鏈表

無環(huán)圖: 單向遍歷不能回到已遍歷的點(diǎn)，比如樹

分類3

帶權(quán)圖: 圖的具有邊帶有關(guān)于該邊信息的權(quán)值，比如地圖中兩點(diǎn)間距離

無權(quán)圖: 圖的每個(gè)邊都不具有有關(guān)于該邊信息的權(quán)值，其僅表示是否連通

其他

單圖: 一個(gè)圖如果任意兩頂點(diǎn)之間只有一條邊且邊集中不含環(huán)，則稱為單圖

圖的表示采用鄰接矩陣和類似樹的形式(頂點(diǎn)指針域是個(gè)指針數(shù)組)的形式，其具有以下特點(diǎn)：

無向圖的鄰接矩陣是對稱矩陣

帶權(quán)圖的矩陣中元素為全職，無權(quán)圖中用0/1分別表示不連通/連通

主對角線有不為零元素，該圖一定有環(huán)

圖的遍歷

廣度優(yōu)先遍歷: 廣度優(yōu)先遍歷是連通圖的一種遍歷策略。因?yàn)樗乃枷胧菑囊粋€(gè)頂點(diǎn) $V_0$ 開始，輻射狀地優(yōu)先遍歷其周圍較廣的區(qū)域。

深度優(yōu)先遍歷:

圖的相關(guān)性質(zhì)：

$N$ 個(gè)頂點(diǎn)的連通圖中邊的條數(shù)至少為 $N-1$

$N$ 個(gè)頂點(diǎn)的強(qiáng)連通圖的邊數(shù)至少有 $N$

廣度優(yōu)先遍歷用來找無權(quán)圖最短路徑（有權(quán)圖其實(shí)也行，多點(diǎn)東西唄）

算法的基本特征：可行性，確定性，有窮性

算法的基本要素：算法中對數(shù)據(jù)的運(yùn)算和操作、算法的控制結(jié)構(gòu)。

算法設(shè)計(jì)的基本方法：窮舉法、動態(tài)規(guī)劃、貪心法、回溯法、遞推法、遞歸法、分治法、散列法，分支限界法。

算法設(shè)計(jì)的要求：正確性、可讀性、健壯性、效率與低存儲量需求

算法的基本結(jié)構(gòu)：順序、循環(huán)、選擇

算法復(fù)雜度

算法的時(shí)間復(fù)雜度：指執(zhí)行算法所需要的計(jì)算工作量(不代表算法實(shí)際需要時(shí)間)

算法的空間復(fù)雜度：執(zhí)行這個(gè)算法所需要的額外內(nèi)存空間(代表算法實(shí)際需要的空間)

復(fù)雜度表示方法: 使用大寫 $O$ 表示：$O(n)$表示時(shí)間復(fù)雜度時(shí)指 $n$ 個(gè)數(shù)據(jù)處理完成使用 $n$ 個(gè)單位的時(shí)間；表示空間復(fù)雜度時(shí)指 $n$ 個(gè)數(shù)據(jù)處理完成使用了 $n$ 個(gè)單位的輔助空間。

字符串算法除了增刪改查以外，還有很多匹配算法，比如最耳熟能詳?shù)?KMP 算法(不屬于基礎(chǔ)部分)，這里整理一些相關(guān)算法的性質(zhì)：

一個(gè)長為 n 的字符串有 $n(n+1)/2+1$ 個(gè)子串

n的字符串，其中的字符各不相同，則S中的互異的非平凡子串有 $frac{1}{2}n^2+frac{1}{2}n-1$ 個(gè)

排序算法實(shí)際上可以分為內(nèi)排序和外排序：

內(nèi)排序：在排序過程中，所有元素調(diào)到內(nèi)存中進(jìn)行的排序，稱為內(nèi)排序。內(nèi)排序是排序的基礎(chǔ)。內(nèi)排序效率用比較次數(shù)來衡量。按所用策略不同，內(nèi)排序又可分為插入排序、選擇排序、堆排序、歸并排序、冒泡排序、快速排序、希爾排序及基數(shù)排序等等。

外排序：在數(shù)據(jù)量大的情況下，只能分塊排序，但塊與塊間不能保證有序。外排序用讀/寫外存的次數(shù)來衡量其效率。

排序算法時(shí)間復(fù)雜度

排序算法分為以下幾類：

插入類排序：插入排序、希爾排序

交換類排序：冒泡排序、快速排序

選擇類排序：選擇排序、堆排序

歸并排序

基數(shù)排序

注:

基數(shù)排序的復(fù)雜度中，$r$ 代表關(guān)鍵字基數(shù)，$d$ 代表長度，$n$ 代表關(guān)鍵字個(gè)數(shù)

排序算法的穩(wěn)定性指在原序列中，$r_i=r_j$，且 $r_i$ 在 $r_j$ 之前，而在排序后的序列中，$r_i$ 仍在 $r_j$ 之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。

查找算法時(shí)間復(fù)雜度

平均查找長度(ASL) = 查找表中第 $i$ 個(gè)元素概率($P_i$) $ imes$ 找到第 $i$ 個(gè)元素時(shí)已經(jīng)比較的次數(shù)($C_i$)