數據結構與演算法
1.基本概念和術語：
（1）數據：是描述客觀事物的符號，是計算機中可以操作的對象，是能被計算機識別，並輸入給計算機處理的符號集。
（2）數據元素：是組成數據的、有一點意義的基本單位，在計算機中通常作為整體處理。也被稱為記錄。
（3）數據項：一個數據元素可以由若干個數據項組成。數據項是數據不可再分的最小單元。
（4）數據對象：是性質相同的數據元素的組合，是數據的子集。
（5）數據結構：是相互之間存在一種或多種特定關係的數據元素的集合
2.邏輯結構與物理結構
（1）邏輯結構：是指數據對象中數據元素之間的相互關係。其實這也是數據結構研究的重點。邏輯結構可分為以下四種：
* 集合結構：集合結構中的數據元素除了同屬於 一個集合外，它們之間沒有其他關係。各個數據元素是平等的，它們的共同屬性是「同屬一個集合」。
* 線性關係：線性關係中的數據元素之間是一對一的關係。
* 樹形關係：樹形結構中的書籍元素之間存在一種一對多的層級關係。
* 圖形關係：圖形結構中的數據元素是多對多的關係。
（2）物理結構：是指數據的邏輯結構在計算機中的存儲形式。
* 順序存儲結構：是把數據元素存放在地址連續的存儲單元里，其數據間的邏輯關係和物理關係是一致的。
* 鏈式存儲結構：是把數據元素存放在任意的存儲單元里，這組存儲單元可以是連續的，也可以是不連續的。數據元素的存儲關係並能反應其邏輯關係，因此需要用一個指針存放數據元素的地址。
3.抽象數據類型
（1）數據類型：是指一組性質相同的值的集合及定義在此集合上的一些操作的總稱。
（2）抽象數據類型（ADT）：是指一個數學模型及定義在該模型上的一組操作
4.演算法
演算法是解決特定問題求解步驟的描述 ，在計算機中表現為指令的有限序列，並且每條指令表示一個或多個操作 。
特性：
（1）輸入輸出：演算法需要0或多個輸入但至少有一個輸出。
（2）有窮性：指演算法在執行有限的步驟之後，自動結束而不會出現無限循環，並且每一個步驟在可接受的時間內完成。
（3）確定性：演算法的每一步驟都具有確定的含義，不會出現二義性。
（4）可行性：演算法的每一步都必須是可行的，也就是說，每一步都能夠通過執行有限次完成。
5.函數的漸進增長
給定兩個函數f(n)和g(n)，如果存在一個整數N，使得對於所有n>N，f(n)總是比 g(n)大，那麼，我們說f(n)的增長漸進快於g(n)。
6.演算法時間複雜度
定義：在進行演算法分析時，語句總的執行次數T(n)是關於問題規模n的函數，進而分析T(n)隨n的變化情況並確定T(n)的數量級。演算法的時間複雜度，也就是演算法的時間度量，記作：T(n) = O(f(n))。它表示隨問題規模n的增大，演算法執行時間的增長率和f(n)的增長率相同，稱作演算法的漸進時間複雜度，簡稱為時間複雜度。其中f(n)是問題規模n的某個函數。
（1） 推導大O階方法
l 用常數1取代運算時間中所有加法常數
l 在修改後的運行次數函數中，只保留最高階項
l 如果最高階項存在且不是1，則去除也這個項相乘的常數。得到的結果就是大O階。
（2） 常數階：無論n為多少，執行時間恆定的演算法，稱之為具有O(1)的時間複雜度，又叫做常數階。對於分支結構而言，無論是真，還是假，執行的次數都是恆定的，不會隨著n的變大而發生變化，所以單純的分支結構（不包含在循環結構中），其時間複雜度也是O(1)。
（3） 線性階：線性階的循化結構會複雜很多。要確定某個 演算法的階次，我們常常需要確定某個特定語句或某個語句集運行的次數。因此，我們要分析演算法的複雜度。關鍵就是要分析循環結構的運行情況。一般一個循環結構的複雜度為O(n)。
（4） 對數階：
int count = 1;
while( count
{
Count *= 2;
}
由於每次count乘以2之後，就距離n更近了一分。也就是說，有多少個2相乘後大於n，則會退出循環。由2x = n得到x = log2n。所以這個循環的時間複雜度為O(logn)。
（5） 平方階：兩個循環嵌套的複雜對為O(n2)。
7.演算法空間複雜度
演算法的空間複雜度通過計算演算法所需的存儲空間實現，演算法空間複雜度的計算公式記作：S(n) = O(f(n))，其中，n為問題的規模，f(n)為語句關於n所佔儲存空間的函數。
一般情況下，一個程序在機器上執行時，除了需要儲存程序本身的指令、常數、變數和輸入輸出外，還需要儲存對數據操作的儲存單元。若輸入數據所佔空間只取決於問題本身，和演算法無關，這樣只需要分析該演算法在實現時所需要的輔助單元即可。若演算法執行時所需的輔助空間相對於輸入數據量而言是個常數，則稱次演算法為原地工作，空間複雜度為O(1)。
重慶大學網路信息協會
TAG:重大開發者 |