以下內(nèi)容整理自互聯(lián)網(wǎng)，僅用于個人學(xué)習(xí)
1. 數(shù)據(jù)結(jié)構(gòu)基本概念
數(shù)據(jù)結(jié)構(gòu)三要素：
- 數(shù)據(jù)的邏輯結(jié)構(gòu)：邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系，即從邏輯關(guān)系上描述數(shù)據(jù)。與數(shù)據(jù)的具體存儲無關(guān)。數(shù)據(jù)的邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)，線性表就是典型的線性結(jié)構(gòu)。集合、樹和圖是典型的非線性結(jié)構(gòu)。
-
數(shù)據(jù)的存儲結(jié)構(gòu)：存儲結(jié)構(gòu)是指數(shù)據(jù)結(jié)構(gòu)在計算機中的表示，也稱物理結(jié)構(gòu)。包括數(shù)據(jù)元素的表示和關(guān)系的表示。
數(shù)據(jù)的存儲結(jié)構(gòu)主要有：順序存儲、鏈?zhǔn)酱鎯?、索引存儲和散列存儲?/li>
- 順序存儲： 把邏輯上相鄰的元素存儲在物理位置上也相鄰的存儲單元里，元素之間的關(guān)系由存儲單元的鄰接關(guān)系關(guān)系來體現(xiàn)。優(yōu)點是可以實現(xiàn)隨機存取，每個元素占用最少的存儲空間；缺點是只能使用相鄰的一款存儲單元，因此可能產(chǎn)生較多的外部碎片。
鏈接存儲：不要求邏輯上相鄰的元素在物理位置上也相鄰， 借助指示元素存儲地址的指針表示元素之間的邏輯關(guān)系。其優(yōu)點是不會出現(xiàn)碎片現(xiàn)象，充分利用所有存儲單元；缺點是每個元素之間因存儲指針而占用額外的空間，并且只能順序讀取。
索引存儲：在存儲元素信息的同時還建立附加的索引表。索引表的每一項稱為索引項，索引項的一般形式是：（關(guān)鍵字，地址）。其優(yōu)點是檢索速度快；缺點是增加了附加的索引表，會占用較多的存儲空間。另外在增加和刪除數(shù)據(jù)時，要修改索引表，因此會花費較多的時間。
散列存儲：根據(jù)元素的關(guān)鍵字，直接計算出該元素的存儲地址，又稱Hash存儲。其優(yōu)點是檢索、增加和刪除節(jié)點的操作都很快；缺點是如果散列函數(shù)不好，可能出現(xiàn)元素存儲單元的沖突，而解決沖突會增加時間。
數(shù)據(jù)的運算：施加在數(shù)據(jù)上的運算包括運算的定義和實現(xiàn)。運算的定義是針對邏輯結(jié)構(gòu)的，指出運算的功能；運算的實現(xiàn)是針對存儲結(jié)構(gòu)的，指出運算的具體操作步驟。
2. 復(fù)雜度分析
2.1 算法
算法是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作。此外，算法還具有下列5個重要特性：
- 有窮性：一個算法必須總是（對于任何合理的輸入值）在執(zhí)行有窮步之后結(jié)束，且每一步都可在有窮時間內(nèi)完成。
- 確定性：算法每一條指令必須有確切的含義，讀者理解時不糊產(chǎn)生二義性。即對相同的輸入只能得出相同的輸出。
- 可行性： 一個算法是可行的，即算法中的描述操作都是可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)。
- 輸 入：一個算法有零個或多個輸入，這些輸入取自于某個特定的對象的集合。
- 輸 出：一個算法有一個或多個輸出，這些輸出是同輸入有著某種特定關(guān)系的量。
2.2 時間復(fù)雜度
將算法中所有語句被重復(fù)執(zhí)行的次數(shù)之和記作T(n)，時間復(fù)雜度主要是分析T(n)的數(shù)量級。記作O(f(n))。假設(shè)f(n)=an3+bn2+c*n則O(f(n))=O(n^3) 看一個例子，假設(shè)需要從數(shù)組A[0···n-1]中查找值K位置，算法大致如下：
i=n-1;
while(i>0&&A[i]!=k){
i--;
}
return i;
此算法的復(fù)雜度不僅與問題規(guī)模n有關(guān)，還與輸入實例中A的各元素取值以及K的取值有關(guān)：
- 如果A中沒有與K相等的元素，則第2行代碼執(zhí)行次數(shù)為f(n)=n
- 如果A的最后一個元素等于K，則第2行執(zhí)行的次數(shù)為f(n)=0；
- 最壞時間復(fù)雜度：是指最壞的情況下，算法的時間復(fù)雜度。
- 最好時間復(fù)雜度：是指最好的情況下，算法的時間復(fù)雜度。
- 平均時間復(fù)雜度：是指所有可能輸入實例等概率出現(xiàn)的情況下，算法的期望運行時間。
一般總是考慮最壞情況下的時間復(fù)雜度，以保證算法的運行時間不會比它更長。 分析算法復(fù)雜度時，有以下兩條規(guī)則：
- 加法規(guī)則：O(f(n))+O(g(n))=O(max(f(n),g(n))
- 乘法規(guī)則：O(f(n))O(g(n))=O(f(n)g(n))
常見的時間復(fù)雜度大小關(guān)系：
O(1) < O(log2n)< O(n) < O(nlog2n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
2.3 空間復(fù)雜度
空間復(fù)雜度為算法所耗費的存儲空間，除了存放本身所用的指令、常數(shù)、變量和輸入數(shù)據(jù)外，還需要一些對數(shù)據(jù)進行操作的工作單元和輔助空間，他是問題規(guī)模n的函數(shù)。 算法原地工作：是指算法所需輔助空間是常量，即O(1)
