一贼急、數(shù)據(jù)結(jié)構(gòu)與算法介紹
1茅茂、程序=結(jié)構(gòu)+算法
程序由存儲(chǔ)數(shù)據(jù)的結(jié)構(gòu)和解決問(wèn)題的算法組成，在計(jì)算機(jī)的世界里太抓，結(jié)構(gòu)和算法存在"相輔相成"的關(guān)系空闲。程序根據(jù)算法選擇最合適的存儲(chǔ)結(jié)構(gòu)，算法依賴存儲(chǔ)結(jié)構(gòu)走敌，選擇最優(yōu)的策略處理數(shù)據(jù)碴倾，達(dá)到占用空間少、計(jì)算時(shí)間少的目的。
2跌榔、邏輯結(jié)構(gòu)與物理結(jié)構(gòu)
數(shù)據(jù)元素之間相互聯(lián)系的方式稱之為邏輯結(jié)構(gòu)异雁，數(shù)據(jù)元素的邏輯結(jié)構(gòu)通過(guò)相互之間的關(guān)系分為：
2.1、集合僧须，元素之間沒(méi)有關(guān)系纲刀，單獨(dú)存在；
2.2担平、線性結(jié)構(gòu)示绊，數(shù)組或鏈表表示的是1對(duì)1的關(guān)系；
2.3暂论、樹(shù)面褐，二叉樹(shù)是1對(duì)2的關(guān)系，普通樹(shù)是1對(duì)多的關(guān)系取胎；
2.4展哭、圖，圖是多對(duì)多關(guān)系闻蛀，節(jié)點(diǎn)表示元素匪傍，邊表示節(jié)點(diǎn)之間的關(guān)系，有向邊可以表示有向圖循榆。
數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)方式是物理結(jié)構(gòu)析恢，數(shù)據(jù)按照在計(jì)算機(jī)中的存儲(chǔ)結(jié)構(gòu)可以分成兩類缘滥，分別是線性存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)限次。
3、常見(jiàn)算法和算法的重要性
例如：計(jì)算1+2+3+...+1000的和
方法一：
Public int add(){
int sum = 0;
for(int i=1;i<=1000;i++){
sum +=i;
}
return sum;
}
方法二：
Public int add(){
int sum = 0普气；
sum = 1000*（1+1000）/2
return sum;
}
分析：
假定方法內(nèi)每一條語(yǔ)句執(zhí)行時(shí)間為1unit_time,
方法一循環(huán)執(zhí)行了(1+2*1000+1)unit_time盗尸，方法二執(zhí)行時(shí)間（1+1+1）unit_time;從上面兩種方式計(jì)算sum柑船，可以得出：好的算法真的很重要
二、時(shí)間復(fù)雜度分析
1泼各、時(shí)間復(fù)雜淺析
漸進(jìn)時(shí)間復(fù)雜度是隨著數(shù)據(jù)規(guī)模N增大而變化的趨勢(shì)鞍时，是衡量一個(gè)算法好壞的標(biāo)準(zhǔn)。時(shí)間復(fù)雜度包含最好時(shí)間復(fù)雜度扣蜻、平均時(shí)間復(fù)雜度逆巍、最壞時(shí)間復(fù)雜度。
Public int find（int[] arr,int n,int data）{
for（int i=0;i<n;i++）{
if(arr[i] == data) {
return i;
break莽使；
}
}
return -1;
}
上面方法是從數(shù)組中查找數(shù)據(jù)锐极，如果找到數(shù)據(jù)返回?cái)?shù)組下標(biāo)，如果沒(méi)找到芳肌，則返回-1灵再。arr是數(shù)組引用肋层，n是數(shù)組長(zhǎng)度，data是待查找數(shù)據(jù)翎迁。
最好時(shí)間復(fù)雜度：當(dāng)開(kāi)始遍歷數(shù)組時(shí)栋猖，正好第一個(gè)數(shù)就是我們需要的查找的數(shù)據(jù)，時(shí)間復(fù)雜度O(1)汪榔；
最壞時(shí)間復(fù)雜度：當(dāng)遍歷完數(shù)組蒲拉，還是沒(méi)有找到我們需要的數(shù)據(jù)，時(shí)間復(fù)雜度O(n)揍异；
平均時(shí)間復(fù)雜度：平均復(fù)雜度計(jì)算方法全陨，(1+2+3+...+n-1+n)/n=n*(n+1)/2n，時(shí)間復(fù)雜度O(n)衷掷。
2、時(shí)間復(fù)雜度大O表示法
推導(dǎo)大O階柿菩，我們可以按照如下的規(guī)則來(lái)進(jìn)行推導(dǎo)戚嗅，得到的結(jié)果就是大O表示法：
1、用常數(shù)1來(lái)取代運(yùn)行時(shí)間中所有加法常數(shù)枢舶。
2懦胞、修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高階項(xiàng)
3凉泄、如果最高階項(xiàng)存在且不是1躏尉，則去除與這個(gè)項(xiàng)相乘的常數(shù)。
常見(jiàn)時(shí)間復(fù)雜度比較：
O（1) < O(lgn) < O(n) < O(nlgn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
三后众、空間復(fù)雜度分析
類似時(shí)間復(fù)雜度胀糜，空間復(fù)雜度是一個(gè)算法占用存儲(chǔ)空間，和數(shù)據(jù)規(guī)模N成漸進(jìn)關(guān)系蒂誉。
空間復(fù)雜度占用空間包含三個(gè)方面：
1教藻、算法本身占用空間；
2右锨、算法輸入輸出占用空間括堤；
3、在計(jì)算的過(guò)程中绍移，臨時(shí)申請(qǐng)的內(nèi)存占用的空間悄窃。
算法在執(zhí)行的過(guò)程中，占用的空間不隨數(shù)據(jù)規(guī)則N變化而變化蹂窖，這樣的算法是"就地"進(jìn)行的轧抗。算法空間復(fù)雜度是一個(gè)常量，占用空間不隨數(shù)據(jù)規(guī)模變化而變化恼策，空間復(fù)雜度則為O(1),分析占用空間方法和時(shí)間復(fù)雜度類似鸦致。
