本文將“資料結構”分為 “資料” 和 “結構” 兩部分。
資料
程式設計 = 資料結構 + 演算法
資料
“資料”是描述客觀事物的符號， 是電腦中可以操作的物件， 是能被電腦識別， 並輸入給電腦處理的符號集合。 也就是說， 我們這裡說的資料其實就是符號， 而且這些符號必須具備兩個前提：
比如， 數值、聲音、圖像、視頻等都是資料。
可以輸入到電腦中
能被電腦程式處理
資料元素
“資料元素”是組成資料的、有一定意義的基本單位， 在電腦中通常作為整體處理。 也被稱為記錄。
比如， 在人類中， 人就是資料元素。
資料項目
一個資料元素可以由若干個資料項目組成。
比如人這個資料元素， 可以有眼、耳、嘴等這些資料項目， 也可以有姓名、年齡、性別等這些資料項目。
資料物件
“資料物件”是性質相同的資料元素的集合， 是資料的子集。
性質相同， 是指資料元素具有相同數量和類型的資料項目。 比如人都有姓名、性別等相同的資料項目。
資料結構
“資料結構”是相互之間存在一種或多種特定關係的資料元素的集合。
它們之間的關係：
資料（資料物件）
|
資料元素
|
資料項目
結構
按照視點的不同， 我們把資料結構分為邏輯結構和物理結構。 邏輯結構是面向問題的， 而物理結構是面向電腦的。
邏輯結構
“邏輯結構”是指數據物件中資料元素之間的相互關係。
邏輯分為四種：
集合結構：
集合結構中的資料元素除了同屬於一個集合外， 它們之間沒有其他關係。
線性結構：
線性結構中的資料元素之間是一對一的關係。
樹形結構：
樹形結構中的資料元素之間存在一對多的層次關係。
圖形結構：
圖形結構的資料元素是多對多的關係。
物理結構
“物理結構”是指數據的邏輯結構在電腦中的存儲形式。
資料元素的存儲結構形式有兩種：順序存儲和鏈式存儲。
順序存儲結構：
把資料元素存放在位址連續的存儲單元裡， 其資料間的邏輯關係和物理關係是一致的。
鏈式存儲結構：
把資料元素存放在任意的存儲單元裡， 這組存儲單元可以是連續的， 也可以是不連續的。
抽象資料類型
資料類型是指一組性質相同的值的集合及定義在此集合上的一些操作的總稱。
在C語言中， 按照取值的不同， 資料類型可以分為兩類：
原子類型：不可以再分解的基本類型， 包括整型、實型、字元型等。
結構類型：由若干個類型組合而成， 是可以再分解的。
抽象資料類型（Abstract Data Type， ADT）：是指一個數學模型及定義在該模型上的一組操作。 它體現了程式設計中問題分解、抽象和資訊隱藏的特性。
抽象資料類型的標準格式：
演算法是解決特定問題求解步驟的描述， 在電腦中表現為指令的有限序列， 並且每條指令表示一個或多個操作。
演算法的特性
演算法具有五個基本特性：輸入、輸出、有窮性、確定性、可行性。
演算法設計的要求
好的演算法， 應該具有：正確性、可讀性、健壯性、高效率和低存儲量的特徵。
函數的漸近增長
輸入規模 n 在沒有限制的情況下， 只要超過一個數值 N， 這個函數就總是大於另一個函數， 我們稱函數是漸近增長的。
給定兩個函數 f(n) 和 g(n), 如果存在一個整數 N，
演算法時間複雜度
在進行演算法分析時， 語句總的執行次數 T(n) 是關於問題規模 n 的函數， 進而分析 T(n) 隨 n 的變化情況並確定 T(n) 的數量級。 演算法的時間複雜度， 也就是演算法的時間量度， 記作：T(n) = O(f(n))。 它表示隨問題規模 n 的增大， 演算法執行時間的增長率和 f(n) 的增長率相同， 稱為演算法的漸近時間複雜度， 簡稱為時間複雜度。 其中 f(n) 是規模 n 的某個函數。
用 O() 來體現演算法時間複雜度的記法， 叫作大 O 記法。
推導大 O 階方法
用常數 1 取代執行時間中的所有加法常數。
在修改後的運行次數函數中， 只保留最高階項。
如果最高階項存在且不是 1 ， 則去除與這個項相乘的常數。
常數階
高斯演算法
這個演算法 的運行次數函數是 f(n) = 3。根據推導大 O 階的方法，第一步把常數項 3 改為 1。第二步保留最高階項，它沒有最高階項，所以這個演算法的時間複雜度為 T(n) = O(1)。
當 n = 1 時，演算法執行次數為 3， 當 n = 100時，演算法的執行次數還是 3，所以我們可以看出這個演算法的執行次數與 n 的規模沒關係。我們把這種與問題的大小（n 的大小）無關，執行時間恒定的演算法， 叫作常數階。
對於分支結構，無論是真還是假，執行的次數都是恒定的，不會隨著 n 的變化而變化，所以單純的分支結構（不包含在迴圈結構中），其時間複雜度也是 O(1)。
線性階
下面這段代碼的時間複雜度為 O(n),因為循環體中的代碼必須要執行 n 次。
對數階
由於每次 count 乘以 2 以後，就越來越接近於 n，也就是說有多少個 2 相乘後大於 n，則會退出迴圈。由 2x = n 等到 x = log2n。所以這個演算法的時間複雜度為 T(n) = O(logn)。
平方階
這是一個迴圈嵌套的代碼。
它的內迴圈我們已經知道，時間複雜度為 O(n)，而對於外層的迴圈，不過是內部這個時間複雜度為 O(n) 的語句，再迴圈 n 次。所以這段代碼的時間複雜度為 O(n2)
如果外迴圈的次數改為了 m，時間複雜度就變為 O(m*n)。
所以我們可以總結得出，迴圈的時間複雜度等於循環體的複雜度乘以該迴圈運行的次數。
下面這個迴圈嵌套，它的時間複雜度是多少呢？
由於當 i = 0 時，內迴圈執行了 n 次，當 i = 1 時，執行了 n -1 次，…… 當 i = n - 1 時，執行了 1 次。所以部的執行次數為：
n + (n-1) + (n-2) + …… + 1 = n(n+1)/2 = n2/2 + n/2。
用我們推導大 O 階的方法，第一條，沒有加法常數不考慮；第二條，只保留最高階項，因此保留 n2/2；第三條，去除這個項相乘的常數，也就是去除 1/2， 最終這個演算法的時間複雜度為 T(n) = O(n2)
常見的時間複雜度
階非正式術語O(1)常數階O(n)線性階O(n2)平方階O(logn)對數階O(nlogn)nlogn階O(n3)立方階O(2n)指數階常用的時間複雜度所耗費的時間從小到大依次是：
O(1)
演算法空間複雜度
演算法的空間複雜度通過計算演算法所需的存儲空間實現，演算法空間複雜度的計算公式：S(n) = O(f(n)),其中 n 為問題的規模，f(n)為語句關於 n 所占存儲空間的函數。
學習Java的同學注意了！！！
學習過程中遇到什麼問題或者想獲取學習資源的話，歡迎加入Java學習交流群495273252，我們一起學Java！
常數階
高斯演算法
這個演算法 的運行次數函數是 f(n) = 3。根據推導大 O 階的方法，第一步把常數項 3 改為 1。第二步保留最高階項，它沒有最高階項，所以這個演算法的時間複雜度為 T(n) = O(1)。
當 n = 1 時，演算法執行次數為 3， 當 n = 100時，演算法的執行次數還是 3，所以我們可以看出這個演算法的執行次數與 n 的規模沒關係。我們把這種與問題的大小（n 的大小）無關，執行時間恒定的演算法， 叫作常數階。
對於分支結構，無論是真還是假，執行的次數都是恒定的，不會隨著 n 的變化而變化，所以單純的分支結構（不包含在迴圈結構中），其時間複雜度也是 O(1)。
線性階
下面這段代碼的時間複雜度為 O(n),因為循環體中的代碼必須要執行 n 次。
對數階
由於每次 count 乘以 2 以後，就越來越接近於 n，也就是說有多少個 2 相乘後大於 n，則會退出迴圈。由 2x = n 等到 x = log2n。所以這個演算法的時間複雜度為 T(n) = O(logn)。
平方階
這是一個迴圈嵌套的代碼。
它的內迴圈我們已經知道，時間複雜度為 O(n)，而對於外層的迴圈，不過是內部這個時間複雜度為 O(n) 的語句，再迴圈 n 次。所以這段代碼的時間複雜度為 O(n2)
如果外迴圈的次數改為了 m，時間複雜度就變為 O(m*n)。
所以我們可以總結得出，迴圈的時間複雜度等於循環體的複雜度乘以該迴圈運行的次數。
下面這個迴圈嵌套，它的時間複雜度是多少呢？
由於當 i = 0 時，內迴圈執行了 n 次，當 i = 1 時，執行了 n -1 次，…… 當 i = n - 1 時，執行了 1 次。所以部的執行次數為：
n + (n-1) + (n-2) + …… + 1 = n(n+1)/2 = n2/2 + n/2。
用我們推導大 O 階的方法，第一條，沒有加法常數不考慮；第二條，只保留最高階項，因此保留 n2/2；第三條，去除這個項相乘的常數，也就是去除 1/2， 最終這個演算法的時間複雜度為 T(n) = O(n2)
常見的時間複雜度
階非正式術語O(1)常數階O(n)線性階O(n2)平方階O(logn)對數階O(nlogn)nlogn階O(n3)立方階O(2n)指數階常用的時間複雜度所耗費的時間從小到大依次是：
O(1)
演算法空間複雜度
演算法的空間複雜度通過計算演算法所需的存儲空間實現，演算法空間複雜度的計算公式：S(n) = O(f(n)),其中 n 為問題的規模，f(n)為語句關於 n 所占存儲空間的函數。
學習Java的同學注意了！！！
學習過程中遇到什麼問題或者想獲取學習資源的話，歡迎加入Java學習交流群495273252，我們一起學Java！