數(shù)據(jù)結(jié)構(gòu) “預(yù)習(xí)” 筆記：第一章 數(shù)據(jù)結(jié)構(gòu)的概念

一、學(xué)習(xí)目標(biāo)

重點(diǎn)理解數(shù)據(jù)結(jié)構(gòu)的定義，邏輯結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)，算法的時(shí)間效率分析和算法的空間效率分析

二、數(shù)據(jù)結(jié)構(gòu)概念知識(shí)

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

1. 概念??

• 數(shù)據(jù)：所有的數(shù)字，字符和能夠被輸入到計(jì)算機(jī)中進(jìn)行運(yùn)算的符號(hào)的集合。

• 數(shù)據(jù)元素：數(shù)據(jù)元素是數(shù)據(jù)的基本單位??，在計(jì)算機(jī)中通常是作為整體進(jìn)行處理的.一個(gè)數(shù)據(jù)的元素可以由多個(gè)數(shù)據(jù)項(xiàng)組成。

• 數(shù)據(jù)項(xiàng)：數(shù)據(jù)的最小單位??，數(shù)據(jù)項(xiàng)是不可分割的。同時(shí)數(shù)據(jù)項(xiàng)也被稱(chēng)為成員或者域

---

數(shù)據(jù)結(jié)構(gòu)：相互之間存在著 特定關(guān)系的數(shù)據(jù)元素的集合 。在這門(mén)課程中常常討論的數(shù)據(jù)結(jié)構(gòu)有：相鄰關(guān)系和鄰接關(guān)系

數(shù)據(jù)結(jié)構(gòu)包括以下三個(gè)方面：

• 邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間的邏輯關(guān)系，這部分面向用戶，與計(jì)算機(jī)無(wú)關(guān)。可以使用樹(shù)或者圖等等用戶容易理解的方式進(jìn)行展示。其分為兩種類(lèi)型：線性和非線性
• 物理結(jié)構(gòu): 面向計(jì)算機(jī)的，對(duì)于邏輯結(jié)構(gòu)的存儲(chǔ)的表示。常見(jiàn)的存儲(chǔ)的方式有：順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、索引存儲(chǔ)、散列存儲(chǔ)。
• 數(shù)據(jù)運(yùn)算: 針對(duì)于數(shù)據(jù)進(jìn)行的運(yùn)算或者處理。

2. My理解??

用圖表對(duì)于這里的概念進(jìn)行理解，當(dāng)前的表即可以理解為邏輯結(jié)構(gòu)。那么表的存儲(chǔ)可以理解為物理結(jié)構(gòu)。若是想要對(duì)于表中的數(shù)據(jù)進(jìn)行操作，便可以算是數(shù)據(jù)運(yùn)算。

2.2 抽象數(shù)據(jù)類(lèi)型ADT（Abstract Data Type）

1. 概念??

• 數(shù)據(jù)類(lèi)型：程序設(shè)計(jì)語(yǔ)言中已經(jīng)實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。一組數(shù)據(jù)的值和對(duì)這組數(shù)據(jù)執(zhí)行的操作的集合的總稱(chēng)。
• 抽象數(shù)據(jù)類(lèi)型ADT：數(shù)據(jù)元素集合以及在這些數(shù)據(jù)上的操作被稱(chēng)做抽象數(shù)據(jù)類(lèi)型。與具體的存儲(chǔ)和具體實(shí)現(xiàn)算法無(wú)關(guān)。數(shù)據(jù)聲明和數(shù)據(jù)運(yùn)算分離。其可以定義一個(gè)完整的數(shù)據(jù)結(jié)構(gòu)。

2. My理解??

簡(jiǎn)單的數(shù)據(jù)類(lèi)型包括整數(shù)、浮點(diǎn)數(shù)、字符、布爾值等。每個(gè)數(shù)據(jù)類(lèi)型有其特定的性質(zhì)和能夠執(zhí)行的操作。
常見(jiàn)的抽象數(shù)據(jù)類(lèi)型包括棧、隊(duì)列、鏈表、樹(shù)、圖等。這些抽象數(shù)據(jù)類(lèi)型為程序員提供了一種高層次的抽象，使得可以在不關(guān)心底層實(shí)現(xiàn)的情況下使用數(shù)據(jù)結(jié)構(gòu)。

舉例來(lái)說(shuō)，棧是一種抽象數(shù)據(jù)類(lèi)型，它定義了一組操作，如壓棧（push）、彈棧（pop），但并沒(méi)有規(guī)定這些操作的具體實(shí)現(xiàn)方式。程序員可以使用棧來(lái)解決問(wèn)題，而無(wú)需關(guān)心棧的具體實(shí)現(xiàn)。

三、算法與算法評(píng)價(jià)概念知識(shí)

3.1 什么是算法

1. 概念??

• 算法 是解決問(wèn)題或執(zhí)行特定任務(wù)的有限步驟的有序集合。簡(jiǎn)而言之，算法是一種清晰定義、可執(zhí)行的計(jì)算過(guò)程，它接受輸入數(shù)據(jù)、通過(guò)一系列的計(jì)算步驟處理這些數(shù)據(jù)，并最終產(chǎn)生輸出結(jié)果。

3.2 算法的特性

1. 概念??

1. 有窮性 ：算法必須在有限步驟內(nèi)終止。這意味著算法的執(zhí)行過(guò)程不能無(wú)限循環(huán)或永不停止。有窮性確保算法對(duì)于輸入的任何有限數(shù)據(jù)集都能夠在有限的時(shí)間內(nèi)執(zhí)行完畢。

2. 確定性 ：算法的每個(gè)步驟必須具有明確定義的操作，且對(duì)于相同的輸入，算法的執(zhí)行過(guò)程必須總是產(chǎn)生相同的輸出。確定性保證了算法的可預(yù)測(cè)性和可控性。

3. 可行性 ：算法必須是可行的，也就是說(shuō)，它必須能夠解決指定問(wèn)題的實(shí)例。算法的任務(wù)是找到問(wèn)題的解決方案，這意味著算法必須在給定的約束條件下能夠產(chǎn)生正確的輸出。

4. 無(wú)二義性 ：算法的每個(gè)步驟必須準(zhǔn)確描述，讓計(jì)算機(jī)知道每個(gè)指令要求完成什么。

5. 輸入： 算法接受輸入，這是算法開(kāi)始執(zhí)行時(shí)所需的信息。輸入是指算法處理的數(shù)據(jù)或信息。輸入可以是0個(gè)，也可以是多個(gè)。??。

6. 輸出 ：算法生成輸出，這是算法在執(zhí)行完畢后產(chǎn)生的結(jié)果。輸出是算法最終解決問(wèn)題的體現(xiàn)。輸出可以是1個(gè)也可以是多個(gè)。??

3.3 評(píng)價(jià)好算法的四個(gè)標(biāo)準(zhǔn)

1. 概念??

1. 正確性 ：正確性是指算法或程序執(zhí)行的結(jié)果是否符合預(yù)期。一個(gè)正確的算法應(yīng)該能夠在給定輸入條件下產(chǎn)生正確的輸出。

2. 可讀性 ：可讀性指的是代碼的清晰度和易讀性?？勺x性好的代碼更容易被人理解和維護(hù)。

3. 通用性 ：通用性表示算法或程序的適用范圍廣泛，不僅能夠解決特定問(wèn)題，還能夠應(yīng)用于更廣泛的場(chǎng)景。

4. 健壯性： 健壯性是指算法或程序?qū)τ诋惓Ｇ闆r的處理能力。一個(gè)健壯的程序能夠在面對(duì)非預(yù)期的輸入或操作時(shí)保持穩(wěn)定運(yùn)行，而不會(huì)導(dǎo)致崩潰或產(chǎn)生不可預(yù)測(cè)的結(jié)果。

3.4 算法的評(píng)價(jià)方法

1. 事后分析統(tǒng)計(jì)方法 ：

   • 對(duì)于算法編寫(xiě)對(duì)于的程序，并進(jìn)行運(yùn)行，統(tǒng)計(jì)其執(zhí)行的時(shí)間。

   • 但是受數(shù)據(jù)源，硬件設(shè)備嚴(yán)重的影響，比較結(jié)果很難用來(lái)衡量算法的優(yōu)劣。

2. 事前分析統(tǒng)計(jì)方法 ：

   • 不考慮算法執(zhí)行后的其他因素的干擾，只對(duì)于當(dāng)前的問(wèn)題的規(guī)模，算法策略和方法等關(guān)鍵因素進(jìn)行統(tǒng)計(jì)。

3.5 算法效率的度量

1. 概念??

時(shí)間復(fù)雜度：

時(shí)間復(fù)雜度是評(píng)估算法運(yùn)行效率的概念。它描述了算法的運(yùn)行時(shí)間和輸入規(guī)模n之間的關(guān)系。當(dāng)問(wèn)題規(guī)模由1到n時(shí)，解決問(wèn)題的算法的CPU時(shí)間也從g(1)到g(n)。則成算法的時(shí)間代價(jià)是g(n)

空間復(fù)雜度：

空間復(fù)雜度是一種用于評(píng)估算法所需的存儲(chǔ)空間與輸入規(guī)模之間關(guān)系的概念。當(dāng)問(wèn)題規(guī)模由1到n時(shí)，解決問(wèn)題的算法所需占用的內(nèi)存空間也以某種單位從f(1)到f(n)，此時(shí)稱(chēng)算法的空間代價(jià)是f(n)。

大O表示法：

定義: 若存在常量$c$和$n_0$ ，對(duì)于任意的 $n>n_0$ 有 $T(n)\le c?f(n)$ 則認(rèn)為：$T(n)\le O(f(n))$

則$O(f(n))$被稱(chēng)為算法復(fù)雜度

2. My理解??

時(shí)間復(fù)雜度和空間復(fù)雜度都可以來(lái)表示算法的算法復(fù)雜度。所以說(shuō)他們都可以用大O表示法進(jìn)行表示。

大O表示法舉例:

$f(n)$	$O(f(n))$
$n$	$O(n)$
$n+2$	$O(n)$
$n^2+n+17$	$O(n^2)$
$2n^2+n+2$	$O(n^2)$
$2^n+n+2$	$O(2^n)$
$\sqrt{n+3}$	$O(\sqrt{n})$

??發(fā)現(xiàn)了什么？當(dāng)前的$f(n)$和$O(f(n))$之間，前者總是小于常數(shù)倍的后者

比如：$n+2\le 2n$， $n^2+n+17\le 2n^2$， $\sqrt{n+3}\le \sqrt{2n}$

那么根據(jù)大O表示法的定義，就可以得到上表的表示。??

3.6 常用的度量和度量間的關(guān)系

1. 常見(jiàn)的度量??

2. 度量之間的關(guān)系??
   

$O(1)<O({\log }_{2}n)<O(\sqrt{n})<O(n)<O(n{\log }_{2}n)<O(n^2)<O(n^3)<O(2^n)<O(n!)$

四、算法和算法評(píng)價(jià)之實(shí)戰(zhàn)演練

1. 基礎(chǔ)概念??

加法規(guī)則:

$T(n)=T_1(n)+T_2(n)=O(f_1(n))+O(f_2(n))=O(max(f_1(n),f_2(n)))$

乘法規(guī)則:

$T(n)=T_1(n)?T_2(n)=O(f_1(n))?O(f_2(n))=O(f_1(n)?f_2(n))$

2. My理解??

加法規(guī)則在循環(huán)不嵌套的時(shí)候使用，取復(fù)雜度的最大值

乘法規(guī)則在循環(huán)中，循環(huán)嵌套時(shí)，進(jìn)行乘積運(yùn)算

當(dāng)然這難以理解。下面是時(shí)間復(fù)雜度的例子，本質(zhì)上時(shí)間復(fù)雜度就是CPU執(zhí)行語(yǔ)句消耗的時(shí)間

在這個(gè)思路上我們繼續(xù)分析下述代碼??

// 假設(shè)CPU按照"行"進(jìn)行執(zhí)行 每一行執(zhí)行時(shí)間是一樣的
// 遇到循環(huán)的時(shí)候，把循環(huán)展開(kāi)成行 
int main(){
    // 1. 一次 一行 
    int n; 
    cin>> n; 
    int s1 = 0;
    int s2 = 0;
    // 2. 下述循環(huán)可以展開(kāi)為 N次 N行 
    for(int i=0;i<n;i++)  
    {
        s1+=2;
    }
    // 4. 所以下述循環(huán)就是 N*N次 N*N行 
    for(int i=0;i<n;i++)
    {
        // 3. 下述循環(huán)展開(kāi)為 N次 N行
        // 每一個(gè)循環(huán)都是 N次 N行 
        for(int j=0;j<n;j++)
        {
            s2++; 
        }
    }
}

那么對(duì)于以上的代碼而言，運(yùn)行的時(shí)間復(fù)雜度是多少呢？

當(dāng)我們幻想著把所有的代碼展開(kāi)的時(shí)候就有：$4+N+N^2$，對(duì)于大O表示法 ：$4+N+N^2<2N^2$。

根據(jù)定義，時(shí)間復(fù)雜度就是 ~ $O(n^2)$

這樣看來(lái)，原來(lái)的兩個(gè)規(guī)則就很好理解了。??

加法規(guī)則

把上述的代碼拆成3段：$T_1(n)=4$，$T_2(n)=N$，$T_3(n)=N^2$

對(duì)應(yīng)的時(shí)間復(fù)雜度: $O_1(n)=1$，$O_2(n)=N$，$O_3(n)=N^2$

所以：由于他們循環(huán)不嵌套: 取最大值，得到時(shí)間復(fù)雜度還是 ~ $O(n^2)$

乘法規(guī)則

得自己品下??

Tips:對(duì)于上面的兩個(gè)循環(huán)由于是嵌套關(guān)系,對(duì)于第一個(gè)循環(huán)有$O_1(n)=N$，第二個(gè)循環(huán)有$O_2(n)=N$

那么對(duì)于這里的代碼片段而言，由于他們循環(huán)嵌套: 取乘積，得到時(shí)間復(fù)雜度是 ~ $O(n^2)$

3. 會(huì)爬了，該起飛了??:

實(shí)際上，上述的核心思想是：計(jì)算了CPU一共執(zhí)行了多少行。

解題步驟如下：

• 對(duì)于代碼進(jìn)行分段：依據(jù)循環(huán)進(jìn)行分段，只考慮最外層。

• 解循環(huán)：將循環(huán)中的遞減邏輯想象為遞增邏輯

• 計(jì)算循環(huán)的時(shí)間復(fù)雜度：

  • 執(zhí)行假設(shè)：假設(shè)當(dāng)前循環(huán)運(yùn)行到了最后一步，并且執(zhí)行了$X$次

  • 條件求解：找到一個(gè)滿足退出循環(huán)的關(guān)系式。得到時(shí)間復(fù)雜度$T$

  • 乘法規(guī)則求解：同樣的方法對(duì)于內(nèi)部的循環(huán)進(jìn)行求解，必要時(shí)，保留上層循環(huán)的最后一步的值。所有值進(jìn)行乘法求解。

• 加法規(guī)則求解：同樣的方法作用于每一個(gè)程序段。

• 答案：根據(jù) 度量之間的關(guān)系 進(jìn)行最終答案的編寫(xiě)
  ps：此處方法有待考究，簡(jiǎn)答勿用??

---

4. 示例

用法

假設(shè)有下面的這段代碼：

int main(){
    // 代碼分段: 第一段 
    int n;
    int s = 0; 
    cin>> n;
    int x = n*n;
    // 代碼分段: 第二段
    for(int i=n-1;i>1;i--)
    {
        s++;
    };
    // 代碼分段: 第三段
    while(x!=1)
    {
        x = x * 2;
    };
    // 代碼分段: 第四段
    for(int k=1;k<=n;k*=2){
        for(int j=1;(j+1)*(j+1)<=n;j++)
        {
            s++;
        }
    };
}

---

• 對(duì)于代碼進(jìn)行分段：如上所示，只關(guān)注最外層的循環(huán)，代碼被分為四段

---

• 解循環(huán)：對(duì)于第二段的遞減邏輯，可以寫(xiě)為如下的遞增邏輯

for(int i=2;i<=n-1;i++)
{
    s++;
};

---

• 計(jì)算循環(huán)內(nèi)的時(shí)間復(fù)雜度

// 代碼分段: 第二段
for(int i=2;i<=n-1;i++)
{
    s++;
};

• 執(zhí)行假設(shè):(執(zhí)行后的值)

循環(huán)執(zhí)行0次時(shí)：循環(huán)內(nèi)i = 2（ps：初始值為2）
循環(huán)執(zhí)行1次時(shí)：循環(huán)內(nèi)i = 3
循環(huán)執(zhí)行2次時(shí)：循環(huán)內(nèi)i = 4
循環(huán)執(zhí)行X次時(shí): 循環(huán)內(nèi)i=X+2

• 條件循環(huán):

當(dāng)程序運(yùn)行剛好結(jié)束時(shí)，此時(shí)滿足：

$X+2=n?1$

??

解得：$X=n?3$

那么時(shí)間復(fù)雜度就是$O(n)$??

---

// 代碼分段: 第三段
x = n*n;
while(x!=1)
{
    x = x * 2;
};

• 執(zhí)行假設(shè):(執(zhí)行后的值)

循環(huán)執(zhí)行0次時(shí)：循環(huán)內(nèi)$x=n^2$（ps：初始值$n^2$）
循環(huán)執(zhí)行1次時(shí)：循環(huán)內(nèi)$x=\frac{n^2}{2}$
循環(huán)執(zhí)行2次時(shí)：循環(huán)內(nèi)$x=\frac{n^2}{4}$
循環(huán)執(zhí)行X次時(shí): 循環(huán)內(nèi)$x=\frac{n^2}{2^X}$

• 條件循環(huán):

當(dāng)程序運(yùn)行剛好結(jié)束時(shí)，此時(shí)滿足：

$\frac{n^2}{2^X}=1$

??

解得：$X=2lo{g}_{2}n$

那么時(shí)間復(fù)雜度就是$O(lo{g}_{2}n)$??

---

// 代碼分段: 第四段
for(int k=1;k<=n;k*=2){
    for(int j=1;(j+1)*(j+1)<=n;j++)
    {
        s++;
    }
};

這是個(gè)雙重循環(huán)??看起來(lái)好逆天

第一重循環(huán)

• 執(zhí)行假設(shè):

循環(huán)執(zhí)行0次時(shí)：循環(huán)內(nèi)$k=1$（ps：初始值$1$）
循環(huán)執(zhí)行1次時(shí)：循環(huán)內(nèi)$k=2$
循環(huán)執(zhí)行2次時(shí)：循環(huán)內(nèi)$k=4$
循環(huán)執(zhí)行X次時(shí): 循環(huán)內(nèi)$k=2^x$

• 條件循環(huán):

當(dāng)程序運(yùn)行剛好結(jié)束時(shí)，此時(shí)滿足：

$2^x=n$

??

解得：$X=lo{g}_{2}n$

那么時(shí)間復(fù)雜度就是$T_1=O(lo{g}_{2}n)$??

結(jié)束了？NONONO??

第二重循環(huán)

• 執(zhí)行假設(shè):

循環(huán)執(zhí)行0次時(shí)：循環(huán)內(nèi)$j=1$（ps：初始值$1$）
循環(huán)執(zhí)行1次時(shí)：循環(huán)內(nèi)$j=2$
循環(huán)執(zhí)行2次時(shí)：循環(huán)內(nèi)$j=3$
循環(huán)執(zhí)行X次時(shí): 循環(huán)內(nèi)$j=X$

• 條件循環(huán):

當(dāng)程序運(yùn)行剛好結(jié)束時(shí)，此時(shí)滿足：

${(X+1)}^2<n$

??

解得：$X=\sqrt{n}?1$

那么時(shí)間復(fù)雜度就是$T_2=O(\sqrt{n})$??

結(jié)束了？NONONO??
乘法規(guī)則求解

$T=O(\sqrt{n}?lo{g}_{2}n)$

---

最后一步：加法規(guī)則求解

取最大值！

所以程序的時(shí)間復(fù)雜度為:

$O(\sqrt{n}?lo{g}_{2}n)$

五、補(bǔ)充

5.1 最好，最壞，平均時(shí)間復(fù)雜度

1. 基礎(chǔ)概念??

最好時(shí)間復(fù)雜度:最好時(shí)間復(fù)雜度是指在最理想情況下，算法執(zhí)行所需的最小時(shí)間。

最壞時(shí)間復(fù)雜度:最壞時(shí)間復(fù)雜度是指在最不利情況下，算法執(zhí)行所需的最大時(shí)間。

平均時(shí)間復(fù)雜度:平均時(shí)間復(fù)雜度是指算法在所有可能輸入情況下執(zhí)行所需時(shí)間的期望值。

2. My理解

類(lèi)似于猜數(shù)字游戲：最好就是一次猜中，最壞就是碰巧避開(kāi)了正確答案??最后才猜中。平均就是期望，就是猜的次數(shù)足夠多的情況下逐漸趨近的那個(gè)值就是期望值。

5.2 空間復(fù)雜度

可以參考下大佬的文章??

空間復(fù)雜度計(jì)算

(ps: 學(xué)渣老哥不想考試~奈何大四不得不預(yù)習(xí)下??)文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-822315.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)預(yù)習(xí)筆記第一章-數(shù)據(jù)結(jié)構(gòu)的概念的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！