數(shù)據(jù)結(jié)構(gòu)概述

• 數(shù)據(jù)結(jié)構(gòu)可以簡(jiǎn)單的理解為數(shù)據(jù)與數(shù)據(jù)之間所存在的一些關(guān)系，數(shù)據(jù)的結(jié)構(gòu)分為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的邏輯結(jié)構(gòu)。

邏輯結(jié)構(gòu)

• 集合結(jié)構(gòu)：數(shù)據(jù)元素同屬于一個(gè)集合，他們之間是并列關(guān)系，無其他的關(guān)系；可以理解為中學(xué)時(shí)期學(xué)習(xí)的集合，在一個(gè)范圍之內(nèi)，有很多的元素，元素間沒有什么關(guān)系
• 線性結(jié)構(gòu)：元素之間存在著一對(duì)一的關(guān)系；可以理解為每個(gè)學(xué)生對(duì)應(yīng)著一個(gè)學(xué)號(hào)，學(xué)號(hào)與姓名就是線性結(jié)構(gòu)
• 樹形結(jié)構(gòu)：元素之間存在著一對(duì)多的關(guān)系，可以簡(jiǎn)單理解為家庭族譜一樣，一代接一代
• 圖形結(jié)構(gòu)：元素之間存在多對(duì)多的關(guān)系，每一個(gè)元素可能對(duì)應(yīng)著多個(gè)元素，或被多個(gè)元素對(duì)應(yīng)，網(wǎng)狀圖

存儲(chǔ)結(jié)構(gòu)

• 順序存儲(chǔ)結(jié)構(gòu)：就是將數(shù)據(jù)進(jìn)行連續(xù)的存儲(chǔ)，我們可以將它比喻成學(xué)校食堂打飯排隊(duì)一樣，一個(gè)接著一個(gè)；
• 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：不是按照順序存儲(chǔ)的，后一個(gè)進(jìn)來的數(shù)只需要將他的地址告訴前一個(gè)節(jié)點(diǎn)，前一個(gè)節(jié)點(diǎn)中就存放了它后面那個(gè)數(shù)的地址，所以最后一個(gè)數(shù)的存儲(chǔ)地址就是為null；可以將這種結(jié)構(gòu)比喻成商場(chǎng)吃飯叫號(hào)，上面的號(hào)碼比喻成是地址，你可以之后后面的地址是什么，上面的其他內(nèi)容就是該節(jié)點(diǎn)的內(nèi)容；
• 區(qū)別：
  • 順序存儲(chǔ)的特點(diǎn)是查詢快，插入或者刪除慢
  • 鏈?zhǔn)酱鎯?chǔ)的特點(diǎn)是查詢慢，插入或者刪除快

算法概述

• 同一問題不同解決方法
• 通過時(shí)間和空間復(fù)雜度判斷算法的優(yōu)劣
• 算法沒有最好的，只有最合適的，學(xué)習(xí)算法是為了積累學(xué)習(xí)思路，掌握學(xué)習(xí)思路，并不是為了解決某問題去記住某種算法；對(duì)于時(shí)間復(fù)雜度與空間復(fù)雜度，現(xiàn)在大多數(shù)開發(fā)情況下，我們都在使用以空間換時(shí)間，耗費(fèi)更多的內(nèi)存，來保證擁有更快的速度。
• 各排序算法復(fù)雜度及穩(wěn)定性：
  

如何理解“大O記法”

對(duì)于算法進(jìn)行特別具體的細(xì)致分析雖然很好，但在實(shí)踐中的實(shí)際價(jià)值有限。對(duì)于算法的時(shí)間性質(zhì)和空間性質(zhì)，最重要的是其數(shù)量級(jí)和趨勢(shì)，這些是分析算法效率的主要部分。而計(jì)量算法基本操作數(shù)量的規(guī)模函數(shù)中那些常量因子可以忽略不計(jì)。例如，可以認(rèn)為 3n^2 和 100n^2 屬于同一個(gè)量級(jí)，如果兩個(gè)算法處理同樣規(guī)模實(shí)例的代價(jià)分別為這兩個(gè)函數(shù)，就認(rèn)為它們的效率“差不多”，都為n^2級(jí)。

時(shí)間復(fù)雜度

一個(gè)算法花費(fèi)的時(shí)間與算法中語(yǔ)句的執(zhí)行次數(shù)成正比例，哪個(gè)算法中語(yǔ)句執(zhí)行次數(shù)多,它花費(fèi)時(shí)間就多。算法中的語(yǔ)句執(zhí)行次數(shù)稱為語(yǔ)句頻度或時(shí)間頻度,記為T(n)。n 稱為問題的規(guī)模，當(dāng) n 不斷變化時(shí)，時(shí)間頻度T(n)也會(huì)不斷變化。但有時(shí)我們想知道它變化時(shí)呈現(xiàn)什么規(guī)律。為此，我們引入時(shí)間復(fù)雜度概念。

一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模 n 的某個(gè)函數(shù),用T(n)表示，若有某個(gè)輔助函數(shù)f(n)，使得當(dāng) n 趨近于無究大時(shí)，T(n)/f(n)的極限值為不等于零的常數(shù)，則稱f(n)是T(n)的同數(shù)量級(jí)函數(shù)。記作T(n)=O(f(n))，稱O(f(n))為算法的漸進(jìn)時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度。

有時(shí)候，算法中基本操作重復(fù)執(zhí)行的次數(shù)還隨問題的輸入數(shù)據(jù)集不同而不同,如在冒泡排序中，輸入數(shù)據(jù)有序而無序，結(jié)果是不一樣的。此時(shí)，我們計(jì)算平均值。

時(shí)間復(fù)雜度基本計(jì)算規(guī)則：

• 基本操作，即只有常數(shù)項(xiàng)，認(rèn)為其時(shí)間復(fù)雜度為O(1)
• 順序結(jié)構(gòu)，時(shí)間復(fù)雜度按加法進(jìn)行計(jì)算
• 循環(huán)結(jié)構(gòu)，時(shí)間復(fù)雜度按乘法進(jìn)行計(jì)算
• 分支結(jié)構(gòu)，時(shí)間復(fù)雜度取最大值
• 判斷一個(gè)算法的效率時(shí)，往往只需要關(guān)注操作數(shù)量的最高次項(xiàng)，其它次要項(xiàng)和常數(shù)項(xiàng)可以忽略
• 在沒有特殊說明時(shí)，我們所分析的算法的時(shí)間復(fù)雜度都是指最壞時(shí)間復(fù)雜度

常用時(shí)間復(fù)雜度：

• 注意：經(jīng)常將log2n（以2為底的對(duì)數(shù)）簡(jiǎn)寫成logn

常見時(shí)間復(fù)雜度之間的關(guān)系：

• 所以時(shí)間消耗由小到大為：O(1) < O(log n) < O(n) < O(nlog n) < O(n^2) < O(2^n) < O(n!) < O(n^n)

案例1：

count = 0;				      (1)for(i = 0;i <= n;i++)	  (2)for(j = 0;j <= n;j++) (3)count++;          (4)

• 語(yǔ)句（1）執(zhí)行1次
• 語(yǔ)句（2）執(zhí)行n次
• 語(yǔ)句（3）執(zhí)行n^2次
• 語(yǔ)句（4）執(zhí)行n^2次
• 時(shí)間復(fù)雜度為：T(n) = 1+n+n^2+n^2 = O(n^2)

案例2：

a = 1; 						(1)
b = 2;						(2)
for(int i = 1;i <= n;i++) { (3)int s = a + b;			(4)b = a;					(5)a = s;					(6)
}	

• 語(yǔ)句（1）、（2）執(zhí)行1次
• 語(yǔ)句（3）執(zhí)行n次
• 語(yǔ)句（4）、（5）、（6）執(zhí)行n次
• 時(shí)間復(fù)雜度為：T(n) = 1+1+4n = o(n)

案例3：

i = 1;		 (1)
while(i<n) {i = i*2; (2)
}	

• 語(yǔ)句（1）的頻度是1
• 設(shè)語(yǔ)句（2）的頻度是f(n)，則2f(n)<=n;f(n)<=log2n,取最大值f(n) = log2n
• 時(shí)間復(fù)雜度為：T(n) = O(log2n)

空間復(fù)雜度

• 算法的空間復(fù)雜度計(jì)算公式：S(n) = 0( f(n) )，其中 n 為輸入規(guī)模，f(n)為語(yǔ)句關(guān)于 n 所占存儲(chǔ)空間的函數(shù)

• 一個(gè)算法在計(jì)算機(jī)存儲(chǔ)器上所占用的存儲(chǔ)空間，包括三個(gè)方面

  • 存儲(chǔ)算法本身所占用的存儲(chǔ)空間
  • 算法的輸入輸出數(shù)據(jù)所占用的存儲(chǔ)空間
  • 算法在運(yùn)行過程中臨時(shí)占用的存儲(chǔ)空間

案例：指定的數(shù)組進(jìn)行反轉(zhuǎn)，并返回反轉(zhuǎn)的內(nèi)容

解法一：

public static int[] reverse1(int[] arr) {int n = arr.length; //申請(qǐng)4個(gè)字節(jié)int temp; //申請(qǐng)4個(gè)字節(jié)for (int start = 0, end = n - 1; start <= end; start++, end--) {temp = arr[start];arr[start] = arr[end];arr[end] = temp;}return arr;
}

• 空間復(fù)雜度為：S(n) = 4+4 = O(8) = O(1)

解法二：

public static int[] reverse2(int[] arr) {int n = arr.length; //申請(qǐng)4個(gè)字節(jié)int[] temp = new int[n]; //申請(qǐng)n*4個(gè)字節(jié)+數(shù)組自身頭信息開銷24個(gè)字節(jié)for (int i = n - 1; i >= 0; i--) {temp[n - 1 - i] = arr[i];}return temp;
}

• 空間復(fù)雜度為：S(n) = 4+4n+24 = O(n+28) = O(n)

根據(jù)大O推導(dǎo)法則，算法一的空間復(fù)雜度為0(1),算法二的空間復(fù)雜度為0(n)，所以從空間占用的角度講，算法一要優(yōu)于算法二。

由于java中有內(nèi)存垃圾回收機(jī)制，并且jvm對(duì)程序的內(nèi)存占用也有優(yōu)化(例如即時(shí)編譯) , 我們無法精確的評(píng)估一個(gè)java程序的內(nèi)存占用情況，但是了解了java的基本內(nèi)存占用，使我們可以對(duì)java程序的內(nèi)存占用情況進(jìn)行估算。

由于現(xiàn)在的計(jì)算機(jī)設(shè)備內(nèi)存一般都比較大，基本上個(gè)人計(jì)算機(jī)都是4G起步，大的可以達(dá)到32G ，所以內(nèi)存占用一般情況下并不是我們算法的瓶頸，普通情況下直接說復(fù)雜度，默認(rèn)為算法的時(shí)間復(fù)雜度。

但是，如果你做的程序是嵌入式開發(fā)，尤其是一些傳感器設(shè)備上的內(nèi)置程序,由于這些設(shè)備的內(nèi)存很小, 一般為幾kb，這個(gè)時(shí)候?qū)λ惴ǖ目臻g復(fù)雜度就有要求了，但是一般做java開發(fā)的，基本上都是服務(wù)器開發(fā), 一般不存在這樣的問題。