什么是數(shù)據(jù)結(jié)構(gòu)？
指數(shù)據(jù)元素之間的關(guān)系。這些關(guān)系可以分為：
集合
線性結(jié)構(gòu)
樹形結(jié)構(gòu)
網(wǎng)狀結(jié)構(gòu)。
邏輯結(jié)構(gòu)分為： 線性結(jié)構(gòu) 和 非線性結(jié)構(gòu)。
集合：除了同屬一個對象外不存在相互關(guān)系。如：汽車上的人除了同輛車彼此間無其他關(guān)系。
線性結(jié)構(gòu)：元素間為嚴(yán)格的一對一關(guān)系，即一個元素有且只有一個前驅(qū)。如：成績表中一個學(xué)生一個成績
樹形結(jié)構(gòu)：元素之間為嚴(yán)格的一對多關(guān)系，即一個元素有且只有一個前驅(qū)，但可以多個后繼。如家譜，行政組織
網(wǎng)狀結(jié)構(gòu)：元素之間存在多對多的關(guān)系，比較復(fù)雜。如：微信朋友圈
如何描述數(shù)據(jù)結(jié)構(gòu)？
使用二元組來描述數(shù)據(jù)結(jié)構(gòu)
Data_structure = (D,R)
D 是元素的有限集
R 是D上所有元素的關(guān)系有限集
下面舉一些例子
線性結(jié)構(gòu)可以用二元組表示為:
linear = (D,R)
D = {A,B,C,D,E,F,G,H}
R = {r}
r = {<A,B>,<B,C>,<C,D>,<D,E>,<E,F>,<F,G>,<G,H>}
樹形結(jié)構(gòu)可以用二元組表示為：
tree = (D,R)
D = {A,B,C,D,E,F,G,H,I,J}
R = {r}
r = {<A,B>,<A,C>,<A,D>,<B,E>,<B,F>,<C,G>,<C,H>,<C,I>,<D,G>}
網(wǎng)狀結(jié)構(gòu)可以用二元組表示為：
nets = (D,R)
D = {1,2,3,4,5}
R = {r}
r = {(1,2),(1,3),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)}
尖括號表示有向線，圓括號表示無向線。
將上面的尖括號或圓括號的元素用線連一下便是對應(yīng)的形狀了。
數(shù)據(jù)結(jié)構(gòu)如何存儲？
順序存儲結(jié)構(gòu)：數(shù)據(jù)元素依次存儲在一組連續(xù)存儲單元當(dāng)中，數(shù)據(jù)邏輯關(guān)系由存儲單元的位置直接體現(xiàn)。
鏈?zhǔn)酱鎯Y(jié)構(gòu)：數(shù)據(jù)元素存儲在任意存儲單元當(dāng)中，而附加的指針域表示元素之間的邏輯關(guān)系
程序 = 算法 + 數(shù)據(jù)結(jié)構(gòu)
數(shù)據(jù)結(jié)構(gòu)離不開算法，下面說說算法
什么是算法？
算法具有五個特性：
有窮性：一個算法必須在有窮的執(zhí)行步驟后結(jié)束，每步都可以在有窮的時間內(nèi)完成。
確定性：算法中每條指令必須明確，任何情況下對于相同輸入都有相同的輸出。
可行性：算法中描述的操作均可以用基本運算的有限執(zhí)行次數(shù)來實現(xiàn)。
輸入：一個算法有0個或者多個輸入，這些輸入是某個特定對象的合集
輸出：一個算法至少有一個輸出，與輸入有著某些特定關(guān)系的量。
如何設(shè)計算法？
正確性：除了語法正確，邏輯上也正確，能達(dá)到預(yù)期的目，最好可以驗證結(jié)果是否正確。
可讀性：方便閱讀，交流，改進(jìn)
健壯性：輸入非法參數(shù)，算法能及時給出錯誤答案，并輸出錯誤提示，同時終止程序。
效率與存儲：執(zhí)行的時間越短越好，使用的空間越少越好，雖然時間和空間總算矛盾的
算法的時間復(fù)雜度
事后統(tǒng)計：將不同的算法編制成程序，然后比較這些程序執(zhí)行的時間。
事前估算：用數(shù)學(xué)方法對算法效率直接分析，常用此方法來判斷時間復(fù)雜度。
事前估算需要考慮的因數(shù)：
1.問題的規(guī)模，排序10個數(shù)字比排序100個數(shù)字時間短
2.編寫的語言，越高級的語言執(zhí)行的效率越低。
3.機(jī)器的速度，80386和i7的速度沒得比
4.算法本身的策略。
由于2,3因數(shù)需要考慮到硬件，軟件（編譯器）等因數(shù)，因此用絕對的機(jī)器運行時間來衡量算法
是不科學(xué)的，所以需要拋開這些因數(shù)，主要研究時間效率與算法所處理的問題規(guī)模n的函數(shù)關(guān)系
當(dāng)隨著問題規(guī)模n增大時，算法執(zhí)行時間的增長率與f(n)的增長率相同，稱為算法的漸進(jìn)時間復(fù)雜度。記作：
T(n) = O(f(n))
執(zhí)行時間 == 執(zhí)行次數(shù)（假設(shè)執(zhí)行一條語句所用的時間相同），另外下面的時間復(fù)雜度都以最壞的情況考慮
下面是常見的時間復(fù)雜度：
常數(shù)階 O(1)
對數(shù)階 O(logn)
線性階 O(n)
平方階 O(n^2)
立方階 O(n^3)
指數(shù)階 O(2^n)
階數(shù)階 O(n!)
爆炸階 O(n^n)
下面兩段代碼是累加求和
1 int sum1(){2 int i,sum=0,n=100; #執(zhí)行了1次3 for(i=0;i<n;i++) #執(zhí)行了n+1次4 sum += i; #執(zhí)行了n次5 }
高斯算法
1 int sum2(){2 int n,sum=0; #執(zhí)行了1次3 sum = n(n+1)/2; #執(zhí)行了1次4 }
上面兩段代碼中 n 是問題的規(guī)模。
第一個算法執(zhí)行次數(shù)為：1 + n+1 + n = 2n+2
隨著問題規(guī)模n的增加，執(zhí)行次數(shù)以線性增加，所以時間復(fù)雜度為O(n)
第二個算法執(zhí)行次數(shù)為：1 + 1 = 2
隨著問題規(guī)模n的增加，執(zhí)行次數(shù)始終為2，所以時間復(fù)雜度為O(1)
所以時間復(fù)雜度計算規(guī)則為：
1.如果執(zhí)行的次數(shù)是常數(shù)，與規(guī)模n無關(guān)，則為O(1)
2.如果執(zhí)行的次數(shù)是多次多項式，取最高項，如：n^3 + n^2 則為O(n^3)
3.如果執(zhí)行的次數(shù)是含有系數(shù)和常數(shù)，可以忽略系數(shù)和常數(shù)，如: 2n^2 + 3 則為O(n^2)
有了上面的法則，來分析下下面這些算法的時間復(fù)雜度，n均代表問題規(guī)模。
1 #define n 10 2 int multiMatrix(int a[n][n],b[n][n],c[n][n]){ 3 for(i=0;i<=n;i++) #執(zhí)行了n+1次 4 for(j=0;j<n;j++){ #執(zhí)行了(n+1)*n次 5 c[i][j] = 0; #執(zhí)行了n^2 6 for(k=0;k<n;k++) #執(zhí)行了n^2*(n+1)次 7 c[i][j] = c[i][j] +a[i][k] * b[k][i]; #執(zhí)行了n^3 8 9 }10 }
T(n) = 2n^3 + 3n^2 + 2n + 1 所以時間復(fù)雜度為O(n^3)
1 int fun(){2 i=1;n=100;3 while(i<n){4 i = i * 2;5 }6 }假設(shè)上面的算法執(zhí)行了x次后停止。則有 2^x >= n，所以 x = log(2)n，所以時間復(fù)雜度為O(logn)
1 void prime(n){ 2 i=2; 3 while( (n%i)!=0 && i*1.0<sqrt(n) ) #如果不能被整除，且小于根號n，則繼續(xù)執(zhí)行 4 i++; 5 6 if(i*1.0>sqrt(n)) 7 printf("%d是個素數(shù)\n",n); 8 else 9 printf("%d不是素數(shù)\n",n);10 11 }
函數(shù)作用判斷n是否為素數(shù)，原理就是遍歷開區(qū)間(1,n)間的數(shù)，然后看看遍歷的數(shù)能否被整除。
事實上如果 n^1/2 (根號n)前不存在一個數(shù)能被n整除，那么n^1/2(根號n)之后的數(shù)也不會被n整除
這是因為對稱性。因此只需要判斷 n^1/2(根號n)之前的數(shù)字是否存在一個能被n整除的數(shù)即可。
所以隨著問題規(guī)模n的增加，執(zhí)行的次數(shù)增長率與 f(n)=n^1/2 的漸進(jìn)增長率相同，所以T(n)=O(n^1/2)
后面還有幾道具有挑戰(zhàn)的題目，這里先講講空間復(fù)雜度：
算法的空間復(fù)雜度
指算法對運算所需要的輔助工作單元和存儲為實現(xiàn)計算所需信息輔助性的空間大小，記作：
S(n) = O(f(n));
這個大小不包括輸入數(shù)據(jù)占用的空間，大小是由具體的實際問題來決定的。
下面一個例子：判斷三個數(shù)字中，哪個數(shù)最大
1 max(int a,b,c){ 2 if(a>b){ 3 if(a>c)return a; 4 else return c; 5 } 6 else{ 7 if(b>c)return b; 8 else return c; 9 }10 }
隨著問題規(guī)模增大,執(zhí)行的次數(shù)也增大，時間復(fù)雜度為O(n)
1 max(int a[3]){2 c=a[0];3 for(i=0;i<3;i++)4 if(a[i]>c)c=a[i];5 6 return c;7 }
隨著問題規(guī)模增大,執(zhí)行的次數(shù)也增大，時間復(fù)雜度也為O(n)
上面兩個例子時間復(fù)雜度相同都為O(n)，但第一個算法無需額外的空間，而第二個算法需要兩個變量輔助。
所以第一個算法空間復(fù)雜度優(yōu)于第二個算法，但是當(dāng)問題規(guī)模不是3 而是100的時候，相信沒人會用第一個
算法，因為會寫到手殘。
歡迎各位轉(zhuǎn)載，請指明出處：http://www.cnblogs.com/demonxian3/p/7075441.html
最后來幾個練習(xí)題，評論附上答案
選擇題
1 int fun(int n){2 i=1,s=1;3 while(s<n)4 s += ++i;5 6 return i;7 }
A. O(n/2) B. O(logn) C. O(n) D.O(n^1/2)
for(int i=0;i<m;i++) for(int j=0;j<n;i++) a[i][j] = i*j;
A. O(m^3) B. O(n^2) C. O(m*n) D.O(m+n)
計算題，設(shè)n為整數(shù)求下面的時間復(fù)雜度
(1)
1 i=1,j=0;2 while(i+j<n)3 if(i>j) j=j+1;4 else i=i+1;
(2)
1 x=91,y=100;2 while(y>0)3 if(x>100){4 x=x-10;5 y=y-1;6 }7 else8 x=x+1;
(3)
1 x=n2 while(x>=(y+1)*(y+1))3 y=y+1;
程序員最高境界：靜若癱瘓，動若癲癇
http://www.cnblogs.com/demonxian3/p/7075441.html
延伸閱讀
- 數(shù)據(jù)結(jié)構(gòu)與算法(c++)——跳躍表(skip list) 2017-05-08
- 常用查找數(shù)據(jù)結(jié)構(gòu)及算法（Python實現(xiàn)） 2017-03-17
- 數(shù)據(jù)結(jié)構(gòu)與算法（五），優(yōu)先隊列 2017-01-06
- 《數(shù)據(jù)結(jié)構(gòu)與算法分析》 第四章 樹（二）---二叉樹,二叉查找樹 2016-12-23
- 用JS描述的數(shù)據(jù)結(jié)構(gòu)及算法表示——棧和隊列（基礎(chǔ)版） 2016-12-15
- 常用查找數(shù)據(jù)結(jié)構(gòu)及算法（Python實現(xiàn)） 2016-12-10
- 數(shù)據(jù)結(jié)構(gòu)與算法（六），圖 2016-12-02
- 數(shù)據(jù)結(jié)構(gòu)與算法（八），查找 2016-10-26
- 數(shù)據(jù)結(jié)構(gòu)與算法（七），排序 2016-10-25
數(shù)據(jù)結(jié)構(gòu)與算法(c++)——跳躍表(skip list)