緒論

基本概念（理解即可）

數據是信息的載體，是描述客觀事物屬性的數、字符及所有能輸入到計算機中并被計算機程序識別
和處理的符號的集合。數據是計算機程序加工的原料。（For Example : 聲音/圖像/字符串等）

數據元素是數據的基本單位，通常作為一個整體進行考慮和處理。
一個數據元素可由若干數據項組成，數據項是構成數據元素的不可分割的最小單位。（For Example : 書籍信息是一個數據元素，其中的書名/價格/作者/ISBN等信息作為一個又一個的數據項）

數據結構是相互之間存在一種或多種特定關系的數據元素的集合。
數據對象是具有相同性質的數據元素的集合，是數據的一個子集。

數據結構三要素

不難知道，數據元素之間都不是孤立存在的，一定存在某種關系，這種數據元素之間的關系我們稱之為結構。根據相關特性一般可以分為以下四種：

• 集合
• 線性結構
• 樹形結構
• 圖狀結構或網狀結構
  他們說明的是數據元素之間的邏輯關系，也叫做：邏輯結構。

那么 數據結構在計算機中的表示（也稱映像），也就被稱作物理結構。它包括數據元素的表示和關系的表示。一般地，我們有以下幾種主要的物理結構：

• 順序存儲（以物理位置相鄰表示邏輯上的相鄰）
• 鏈式存儲（形成鏈狀）
• 索引存儲（建立索引表）
• 散列存儲（根據關鍵字算存儲位置）

施加在數據上的運算包括運算的定義（邏輯）和實現（物理）被稱之為數據的運算。

數據類型、抽象數據類型

數據類型是一個值的集合和定義在此集合上的一組操作的總稱。
原子類型：其值不可再分的數據類型。(如bool & int)
結構類型：其值可以再分解為若干成分（分量）的數據類型。(如class等)
抽象數據類型（Abstract Data Type，ADT）：抽象數據組織及與之相關的操作。

ADT用數學化的語言定義數據的邏輯結構、定義運算。與具體的實現無關。

算法和算法分析

算法

算法（Algorithm）是對特定問題求解步驟的一種描述，它是指令的有限序列，其中的每條指令表示一個或多個操作。從定義上和實際，他應具備如下五種特性：

• 有窮性。一個算法必須總在執行有窮步之后結束，且每一步都可在有窮時間內完成。
• 確定性。算法中每條指令必須有確切的含義，對于相同的輸入只能得出相同的輸出。
• 可行性。算法中描述的操作都可以通過已經實現的基本運算執行有限次來實現。
• 輸入。一個算法有零個或多個輸入，這些輸入取自于某個特定的對象的集合。
• 輸出。一個算法有一個或多個輸出，這些輸出是與輸入有著某種特定關系的量。

對于一個”好“算法一定要達到以下目標：

• 正確性。算法應能夠正確地解決求解問題。
• 可讀性。算法應具有良好的可讀性，以幫助人們理解
• 健壯性。輸入非法數據時，算法能適當地做出反應或進行處理，而不會產生莫名其妙的輸出結果。
• 高效率（時間復雜度低）與低存儲量需求（空間復雜度低）

算法效率的度量

時間復雜度

一個語句的頻度是指改語句在算法中被重復執行的次數。算法中所有語句的頻度之和被記為$T(n)$。他是關于該算法問題規模n的函數，時間復雜度主要分析$T(n)$的數量級。算法中基本運算（最深層的語句）的頻度與$T(n)$同數量級每一次通常將算法中基本運算的執行次數的數量級作為該算法的時間復雜度。于是時間復雜度可以定義為：

$$T(n)=O(f(n))$$

當然，最終我們寫出的時間復雜度應取隨n增長最快的項，將其系數置為1作為時間復雜度的度量，例如$f(n)=3n^2+2n+1$，則$T(n)=O(n^2)$。

在分析時間復雜度的時候，有以下兩條規則：

• 加法規則：$T(n)=T_1(n)+T_2(n)=O(f(n))+O(g(n))=O(\max (f(n),g(n)))$
• 乘法規則：$T(n)=T_1(n)\times T_2(n)=O(f(n))\times O(g(n))=O(f(n)\times g(n))$

常見的漸進時間復雜度有：

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

圖像表示：

相應的我們還有如下定義：

最壞時間復雜度：最壞情況下算法的時間復雜度
平均時間復雜度：所有輸入示例等概率出現的情況下，算法的期望運行時間
最好時間復雜度：最好情況下算法的時間復雜度

空間復雜度

算法的空間復雜度$S(n)$定義為該算法所需的存儲空間，他是一個關于算法問題規模n的函數。記為：

$$S(n)=O(f(n))$$

他的計算方法與時間復雜度類似，主要分析算法中基本存儲單元的使用情況。空間復雜度的計算也有加法和乘法規則。（不在贅述在此）

一個程序在執行時除了需要存儲空間來存放自身所用的指令、常數、變量和輸入數據外，還需要一些對數據進行操作的工作單元和存儲一些為實現計算所需信息的輔助空間。若輸入數據所占空間只取決于問題本身，和算法無關，則只需要分析除輸入和程序之外的額外空間。如果算法原地工作是指算法所需的輔助空間為常量，即$S(n)=O(1)$。

也就是說：空間復雜度為$O(1)$代表算法所需輔助空間的大小與問題規模無關。

舉例：

void test(int n){int a[n];int i;
}

上面代碼中，數組a的大小與n有關，因此空間復雜度為$O(n)$。

void test(int n){int i;
}

上面代碼中，變量i的大小與n無關，因此空間復雜度為$O(1)$。

void test(int n){int a[n][n];
}

上面代碼中，數組a的大小與n有關，因此空間復雜度為$O(n^2)$。

void test(int n){int a[n];int b[n][n];int i;
}

上面代碼中，數組a的大小與n有關，數組b的大小與n有關，因此空間復雜度為$S(n)=O(n^2)+O(n)+O(1)$，根據加法原則：$S(n)=O(n^2)$