人妻熟女一区二区,久久结波衣在线

1.數(shù)據(jù)結(jié)構(gòu)的概念

存儲(chǔ)數(shù)據(jù)和數(shù)據(jù)之間的關(guān)系的一個(gè)集合。不僅存儲(chǔ)數(shù)據(jù)，還支持?jǐn)?shù)據(jù)的訪問和操作（添加，刪除）。

Java語言描述：

? ? 抽象數(shù)據(jù)類型（ADT），帶有一組操作的一些對(duì)象的集合

2.數(shù)據(jù)結(jié)構(gòu)的概念關(guān)系圖

數(shù)據(jù)結(jié)構(gòu)概念關(guān)系圖

2.1順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)比較：

順序存儲(chǔ)：開辟一段連續(xù)空間存儲(chǔ)順序表，相鄰數(shù)據(jù)的地址也是相鄰的，要求存儲(chǔ)內(nèi)存中存儲(chǔ)單元地址是連續(xù)的。

? ? 優(yōu)點(diǎn)：存儲(chǔ)密度大（=1），存儲(chǔ)空間利用率高，便于查找數(shù)據(jù)（因?yàn)樗袛?shù)據(jù)都按順序排放，想查詢第幾個(gè)就可以查詢第幾個(gè)）

? ? 缺點(diǎn)：不便于插入和刪除，因?yàn)椴迦胄枰谥付ㄎ恢貌迦?，后面的?shù)據(jù)都要相應(yīng)后移，刪除時(shí)后面所有數(shù)據(jù)要相應(yīng)前移。

鏈?zhǔn)酱鎯?chǔ)：相鄰數(shù)據(jù)可以隨意存放，一個(gè)存儲(chǔ)單元中不僅存儲(chǔ)節(jié)點(diǎn)值，還存儲(chǔ)指向下一節(jié)點(diǎn)的指針（java中描述的是下一節(jié)點(diǎn)的鏈）

? ? 優(yōu)點(diǎn)：便于刪除和插入數(shù)據(jù)，插入數(shù)據(jù)時(shí)只需要將上一個(gè)位置的指針指向該數(shù)據(jù)，將該數(shù)據(jù)的指針指向下一位置；刪除時(shí)只需將指向該節(jié)點(diǎn)的上一節(jié)點(diǎn)的指針指向該節(jié)點(diǎn)指向的下一節(jié)點(diǎn)數(shù)據(jù)。

? ? 缺點(diǎn)：存儲(chǔ)密度?。?lt;1），存儲(chǔ)空間利用率低，因?yàn)椴粌H存儲(chǔ)數(shù)據(jù)還要存儲(chǔ)指針，數(shù)據(jù)的查找不方便

2.2數(shù)據(jù)邏輯結(jié)構(gòu)概述（后面會(huì)詳細(xì)學(xué)習(xí)）：

? ? 集合：數(shù)據(jù)結(jié)構(gòu)中的元素除了存儲(chǔ)于一個(gè)集合中，沒有其他的關(guān)系；

? ? 線性結(jié)構(gòu):數(shù)據(jù)結(jié)構(gòu)中的元素存在一對(duì)一的關(guān)系；

? ? 樹形結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在一對(duì)多的關(guān)系；

? ? 圖形結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在多對(duì)多的關(guān)系；

3.算法分析

算法是為求解一個(gè)問題需要遵循的、被清除指定的簡(jiǎn)單指令的集合。一種算法若是正確的，重要的一步便是確定該算法的時(shí)間復(fù)雜度和空間復(fù)雜度。

3.1時(shí)間復(fù)雜度（執(zhí)行該算法所需要的計(jì)算量，一般考慮最壞情況的運(yùn)行時(shí)間而非平均運(yùn)行時(shí)間）

算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)，用T(n)表示，若有某個(gè)輔助函數(shù)f(n)，使得T(n)/f(n)的極限值（當(dāng)n趨近于無窮大時(shí)）為不等于零的常數(shù)，則稱f(n)是T(n)的同數(shù)量級(jí)函數(shù)。記作T(n)=O(f(n))，稱O(f(n)) 為算法的漸進(jìn)時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度。

隨著模塊n的增大，算法執(zhí)行的時(shí)間的增長(zhǎng)率和 f(n) 的增長(zhǎng)率成正比，所以 f(n) 越小，算法的時(shí)間復(fù)雜度越低，算法的效率越高。?f(n)是T(n)的一個(gè)上界。

重要法則：

? ? 1）若T1(n)=O(f(n))，T2(n)=O(g(n))，則T1(n)+T2(n)=O(f(n)+g(n));

? ? 2）若T1(n)=O(f(n))，T2(n)=O(g(n))，則T1(n)*T2(n)=O(f(n)*g(n));

注意：

? ? 1）不能將常數(shù)或者低階項(xiàng)放進(jìn)大O

? ? 2)? 總能夠通過計(jì)算極限來確定兩個(gè)函數(shù)的相對(duì)增長(zhǎng)率

3.2時(shí)間復(fù)雜度的計(jì)算

在計(jì)算時(shí)間復(fù)雜度的時(shí)候，先找出算法的基本操作，然后根據(jù)相應(yīng)的各語句確定它的執(zhí)行次數(shù)，再找出 T(n) 的同數(shù)量級(jí)（它的同數(shù)量級(jí)有以下：1，log2n，n，n log2n ，n的平方，n的三次方，2的n次方，n!），找出后，f(n) = 該數(shù)量級(jí)，若 T(n)/f(n) 求極限可得到一常數(shù)c，則時(shí)間復(fù)雜度T(n) = O(f(n))。

簡(jiǎn)化分析：拋棄一些前導(dǎo)常數(shù)，拋棄低階項(xiàng)，要計(jì)算的就是大O運(yùn)算時(shí)間。

一般法則：

? ? 1）for循環(huán)：運(yùn)行時(shí)間至多是for循環(huán)內(nèi)部語句的運(yùn)行時(shí)間乘以迭代次數(shù)。

? ? 2）嵌套for循環(huán)：從里向外分析，循環(huán)內(nèi)部語句執(zhí)行時(shí)間乘以該組所有for循環(huán)大小。

? ? 3）順序語句：各個(gè)語句運(yùn)行時(shí)間求和即可，這意味著，最大值便是所得運(yùn)行時(shí)間。

? ? 4）遞歸語句：求解一個(gè)遞推關(guān)系

3.3最大子序列和的問題求解（演示不同時(shí)間復(fù)雜度的算法）

問題描述：給定一組整數(shù)，A1,A2,A3,..AN,求 $\sum_{k=i}^j$ Ak的最大值。