01.緒論
1. 概念
1.1 資料結構
- 資料 Data：資訊的載體，能被計算機識別并處理的符號的集合，
- 資料元素 Data element：資料的基本單位，通常作為一個整體進行考慮和處理，一個資料元素往往由若干資料項組成，資料項是組成資料元素的不可分割的最小單位，
如學生的資訊記錄就是一個資料元素，它由學號、姓名、性別等組成，
-
資料物件 Data object：具有相同性質的資料元素的集合，是資料的一個子集，
-
資料型別 Data type：一個值的集合和定義在此集合上的一組操作的總稱，
- 抽象資料型別ADT(
Abstract Data Type)：一個數學模型（邏輯結構）及在其上定義的一組操作，
- 抽象資料型別ADT(
-
資料結構 Data structure：相互之間存在一種或多種特定關系的資料元素的集合，資料結構包含三方面內容：邏輯結構、存盤結構、資料的運算，
- 邏輯結構： 資料結構的邏輯抽象、資料元素之間的數學關系.
- 存盤結構： 又稱存盤映像或結點，資料結構在計算機中的表示，也稱物理結構.
::: tip 結點與節點
結點：資料結構的物理存盤結構.
節點：在計算機網路中通常指擁有資料存盤、轉發能力的計算機設備終端.
在資料結構中兩者可以通用，但前者常用.
:::
1.2 演算法
1. 定義
演算法通常是指按照一定規則解決某一類問題的明確和有限的步驟，
演算法組成要素：操作、控制結構、資料結構
- 操作：
- 算術運算：加、減、乘、除，
- 關系比較：大于、小于、等于、不等于，
- 邏輯運算：與、或、非，
- 資料傳輸：輸入、輸出、賦值（計算），
- 演算法的控制結構：
演算法的控制結構給出了演算法的框架，決定了各操作的執行順序，- 順序結構：個操作依次進行，
- 選擇結構：有條件是否成立來決定選擇執行，
- 回圈結構：有些操作要重復執行，直到滿足某個條件才結束，這種控制結構也稱為重復或迭代結構，
- 資料結構：
演算法操作的物件是資料，資料的邏輯關系、存盤方式和處理方式即是資料結構，
2. 特性
演算法是滿足下列性質的指令序列.
- 有窮性：一個演算法總是執行有窮步數后結束，且每一步都在有窮時間內完成，
- 確定性：演算法中每條指令必須有確切含義，沒有二義性，只有唯一一條執行路徑，對于相同的輸入只有相同的輸出，
- 可行性：演算法是可執行的，其操作可以通過已經實作的基本操作執行有限次來實作，
- 輸入：一個演算法有零個或多個輸入，
- 輸出：一個演算法有一個或多個輸出，
3. 演算法設計要求
- 正確性 correctness
- 沒有語法錯誤
- 對于精心選擇的，苛刻的***難的資料也能輸出正確的結果
- 程式對于一切合法的輸入資料都能得到正確的輸出結果
- 可讀性 readability
- 健壯性 robustness
- 指當輸入非法資料的時候，演算法能夠恰當的做出反應或進行相應處理，而不是輸出莫名其妙的結果
- 處理出錯的方法，不應是中斷程式的執行，而應是回傳一個表示錯誤或者錯誤性質的值，以便在更高抽象層次上進行處理
- 高效性 efficiency
要求演算法花費盡量少的時間（時間效率）和盡量低的存盤需求（空間效率），
4. 計算機問題求解步驟
- 分析問題： 分析問題的輸入、要求和輸出.
- 資料結構設計： 選擇或設計能有效表示和存盤問題所涉及的資料物件的、能支持演算法實作的資料結構.
- 演算法設計： 選擇演算法策略、描述和逐步細化演算法步驟.
- 演算法分析： 完善改進資料結構和演算法.
- 程式實作： 用某種編程語言定義資料結構、撰寫實作演算法的代碼并運行除錯.
2. 資料結構的兩種層次
2.1 邏輯結構
描述資料元素之間的邏輯關系，與資料的存盤無關，獨立于計算機；是從具體問題抽象出來的數學模型，
1. 線性結構
有且僅有一個開始和一個終端結點，并且所有結點都最多只有一個直接前趨和一個直接后繼，
例如：線性表、堆疊（特殊線性表）、佇列（特殊線性表）、串、陣列、廣義表等
2. 非線性結構
一個結點可能有多個直接前趨和直接后繼，
例如：樹 (一對多) 和 圖 (多對多)
- 集合結構：資料元素除了“同屬一個集合”外沒有其他關系.
- 樹：資料元素存在一對多的關系. 棋盤預測分析，資料像樹木一樣展開
- 圖：資料元素存在多對多關系. 地圖最短路徑，資料像一張網格一樣錯綜復雜
2.2 存盤結構（物理結構）
資料元素及其關系在計算機存盤器中的結構（存盤方式），
1. 順序存盤結構
用一組連續的存盤單元依次存放資料，資料元素之間的邏輯關系由元素的存盤位置來表示
C語言中的陣列、C++中的vector容器都是順序存盤結構
- 優點： 實作隨機存取、每個元素占用最少的存盤空間
- 缺點： 只能使用相鄰的一整塊存盤單元，可能產生較多的外部碎片
2. 鏈式存盤結構
存盤空間不連續，元素之間的邏輯關系用結點的指標表示，
- 優點： 不會出現碎片現象，充分利用所有存盤單元，在表示各種邏輯結構時往往比順序結構更加方便，
- 缺點： 指標額外占用存盤空間、只能實作順序存取，
3. 索引存盤結構
建立附加的索引表，其中每項稱為索引項
- 優點： 檢索速度快，
- 缺點； 索引表額外占用存盤空間，增刪資料也要修改索引表
4. 散列(哈希)存盤結構
根據元素的關鍵字直接計算出該元素的存盤地址
- 優點： 檢索、增刪改查結點的操作都很快，
- 缺點： 若散列函式不好，可能出現存盤單元沖突，解決沖突會增加時間和空間開銷，
3. 演算法和演算法分析
3.1 時間復雜度
-
一個陳述句的頻度是該陳述句在演算法中被重復執行的次數，
-
演算法運行時間=
$$\sum_{
\begin{subarray}{l}
\end{subarray}}陳述句的頻度×陳述句執行一次所需時間$$ -
演算法中所有陳述句的頻度之和記為
T(n)，它是問題規模n的函式，時間復雜度主要分析T(n)的數量級，演算法中基本運算（最深層回圈內的陳述句）的頻度與
T(n)同數量級，用
f(n)表示演算法中的基本運算的頻度，
若有某個輔助函式f(n)，使得當n趨近于無窮大時，T(n)/f(n)的極限值為不等于0的常數，則稱f(n)是T(n)的同數量級函式，記作T(n)=O(f(n))，稱O(f(n))為演算法的漸進時間復雜度（O是數量級的符號），簡稱時間復雜度
用 O(f(n)) 表示 f(n) 中隨 n 增長最快的項，將其系數置1作為時間復雜度的度量（漸進時間復雜度），
T(n)=O(f(n)) 如f(n)=an3+bn2，則時間復雜度為O(n^3)
::: tip 問題規模n的含義
- 回圈：條件判斷執行次數
- 排序：n為陣列中元素個數
- 矩陣：n為矩陣階數或行列數
- 多項式：n為多項式的項數
- 集合：n為元素個數
- 樹：n為樹的節點個數
- 圖：n為圖的頂點數或邊數
:::
計算時間復雜度重點是找到問題規模n與基本陳述句頻度t之間的數學關系，
::: tip 時間復雜度具體求法
- 回圈主體中的變數參與回圈條件的判斷
- 找出基本操作
- 設基本操作執行次數為T(n)，根據初始條件和基本操作陳述句確定變數與次數的關系式
- 帶回回圈條件，求出T(n)，確定O(n)
- 回圈主體中的變數與回圈條件無關
- 遞回程式
- 確定遞推關系（注意這里確定的是基本操作次數的遞推關系，不要和變數的值搞混）
- 推出遞推關系與執行次數的運算式
- 令低級遞推關系中的次數為常數（0或1），整理式子
- 推匯出T(n)
- 非遞回程式
- 等比、等引數列求和
:::
- 等比、等引數列求和
- 遞回程式
平均時間復雜度A(n)
- 最壞情況下的時間復雜度W(n).
演算法求解輸入規模為 n 的實體所需要的最長時間. - 平均狀況下的時間復雜度A(n).
在給定同樣規模為 n 的輸入實體的概率分布下，演算法求解這些實體所需要的平均時間.
設 S 是規模為 n 的實體集，實體 I∈S 的概率是 P_I
演算法對實體I執行的基本運算次數是 t_I
在某些情況下可以假定每個輸入實體概率相等.
example1
x=0,y=0 //1次
for(int k=0;k<n;k++) //n+1(判斷陳述句執行n+1，回圈體執行n)
x++; //n
for(int i=0;i<n;i++) //n+1
for(int j=0;j<n;j++) //n(n+1)
y++; //n*n
T(n)=O(n^2)
example2
for (i=1;i<n;i++) //
for (j=1;j<=i;j++)
for (k=1;k<=j;k++)
x=x+1;
第二重是 j 到 i，j是變數，相當于 1+2+3+…+i 等于i*（i+1）/2
example3
i=1;
while (i<=n)
i=i*2;//找出基本運算
設回圈體執行次數為 $x$ ，令 $2^x≤n$，得$x≤log_2n$
$T(n)=O(log_2n)$
有時，$f(n)$（基本操作執行次數）隨問題的輸入資料集的不同而不同，
::: tip 加法規則和乘法規則
將復雜演算法分解為幾個部分，有
- 順序：T(n)=T1(n)+T2(n)=O(max(
f(n)+g(n))) - 嵌套、回圈：T(n)=T1(n)*T2(n)=O(
f(n)*g(n))
:::
漸進時間復雜度按遞增順序：
O(1) < O(log2n) < O(n) < O(nlog2n) < O(n^k) < O(2^n) < O(n!) < O(n^n)
3.2 空間復雜度
空間復雜度：該演算法所耗費的存盤空間，它是問題規模n的函式，
S(n)=O(g(n)).
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/550435.html
標籤：其他