一. 基本概念
先來一下數(shù)據(jù)結(jié)構(gòu)中基本的概念。
- 數(shù)據(jù)
數(shù)據(jù)是客觀事物的符號(hào)表示纯命。在計(jì)算機(jī)學(xué)科中指的是所有能輸入到計(jì)算機(jī)中被計(jì)算機(jī)程序處理的符號(hào)的總稱堪旧。
- 數(shù)據(jù)元素
數(shù)據(jù)元素是數(shù)據(jù)的基本單位涩禀。在程序中通常作為一個(gè)整體進(jìn)行考慮和處理。
- 數(shù)據(jù)項(xiàng)
一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成咆繁。數(shù)據(jù)項(xiàng)是數(shù)據(jù)不可分割的最小單位讳推。
- 數(shù)據(jù)對(duì)象
數(shù)據(jù)對(duì)象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集玩般。
- 數(shù)據(jù)結(jié)構(gòu)
指相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合银觅。
- 邏輯結(jié)構(gòu)
元素之間的相互關(guān)系稱為邏輯結(jié)構(gòu)。邏輯結(jié)構(gòu)有四種基本類型：集合坏为、線性結(jié)構(gòu)究驴、樹形結(jié)構(gòu)镊绪、圖形（網(wǎng)狀）結(jié)構(gòu)。如圖：
- 物理結(jié)構(gòu)
數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的存儲(chǔ)包括數(shù)據(jù)元素的存儲(chǔ)和元素之間關(guān)系的存儲(chǔ)洒忧，元素之間關(guān)系的存儲(chǔ)稱為物理結(jié)構(gòu)蝴韭。
物理結(jié)構(gòu)有兩種不同的存儲(chǔ)結(jié)構(gòu)。分別為順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)熙侍。
順序結(jié)構(gòu)：數(shù)據(jù)元素存放的地址是連續(xù)的榄鉴。
連式結(jié)構(gòu)：數(shù)據(jù)元素存放的地址是否連續(xù)沒有要求。
數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)是密不可分的蛉抓，算法的設(shè)計(jì)取決于采用的邏輯結(jié)構(gòu)庆尘，算法的實(shí)現(xiàn)依賴于采用的物理結(jié)構(gòu)。
下圖描述了數(shù)據(jù)邏輯結(jié)構(gòu)的層次關(guān)系：
二. 算法分析巷送。
- 算法的設(shè)計(jì)要求：
正確性
健壯性
可讀性
時(shí)間效率高和存儲(chǔ)量低 - 大O表示法的規(guī)則
通常分析算法的時(shí)間復(fù)雜度和空間復(fù)雜度驶忌，使用大O表示法。規(guī)則如下：
(1) 用常數(shù)1表示運(yùn)行時(shí)間中的常數(shù)笑跛。
(2) 表示運(yùn)行時(shí)間的運(yùn)算中位岔，只保留最高階項(xiàng)。
(3) 如果在最高階存在且不等于1堡牡，則去除這個(gè)項(xiàng)目相乘的常數(shù)
- 時(shí)間復(fù)雜度分析
時(shí)間復(fù)雜度有：
常數(shù)階：O(1)
線性階：O(n)
對(duì)數(shù)階：O(*log*n)
線性對(duì)數(shù)階：O(n*log*n)
k次方階：O(n^k)
下圖用橫軸代表n，縱軸代表執(zhí)行時(shí)間復(fù)雜度杨刨，我們分析算法的時(shí)間復(fù)雜度往往是按照最壞情況來考慮晤柄，當(dāng)n趨向無窮大的時(shí)候，可以看出以上幾種表達(dá)式的時(shí)間復(fù)雜度的大醒汀：
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3)
下面來看幾個(gè)例子：
- 以下時(shí)間復(fù)雜度：
O(1)芥颈，因?yàn)?code>x和y都是常數(shù)。
int x=90;
int y=100;
while(y>0){
if(x>100) {
x=x-10;
y--;
}else{
x++;
}
}
- 以下時(shí)間復(fù)雜度：
O(n^2)赚抡，s+=B[i][j];的執(zhí)行次數(shù)為n^2爬坑。
int s=0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++) s+=B[i][j];
}
sum = s;
- 以下時(shí)間復(fù)雜度：
O(log?n)
i = 1;
while(i<=n){
i=i*3;//執(zhí)行次數(shù)f(n)。3^f(n)<=n涂臣。f(n) = log?n盾计。
}
- 以下時(shí)間復(fù)雜度：
O(√x)。
x=n;//n>1
y=0;
while(x>= (y+1)*(y+1))
y++;//執(zhí)行次數(shù)f(n)赁遗。x>=(f(n)+1)2署辉。f(n)=√x -1。忽略常數(shù)岩四。
- 空間復(fù)雜度
算法的空間復(fù)雜度一般是指算法的輔助空間哭尝。
一位數(shù)組a[n]的空間復(fù)雜度：O(n)
二維數(shù)組a[n][m]的空間復(fù)雜度：O(n*m)
