1.1 概念回顧

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

概述

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ),組織數(shù)據(jù)的方式.數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合.通常情況下,精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來(lái)更高的運(yùn)行或者存儲(chǔ)效率.

劃分

從關(guān)注的維度看,數(shù)據(jù)結(jié)構(gòu)可以劃分為數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu),同一邏輯結(jié)構(gòu)可以對(duì)應(yīng)不同的存儲(chǔ)結(jié)構(gòu).
邏輯結(jié)構(gòu)反應(yīng)的是數(shù)據(jù)元素之間的邏輯關(guān)系,邏輯關(guān)系是指數(shù)據(jù)元素之間以什么形式互相關(guān)聯(lián),這與他們?cè)谟?jì)算機(jī)中的存儲(chǔ)位置無(wú)關(guān).邏輯結(jié)構(gòu)包括:

1. 集合:只是扎堆湊在一起,沒(méi)有互相之間的關(guān)聯(lián)
2. 線性結(jié)構(gòu):一對(duì)一關(guān)聯(lián),隊(duì)形
3. 屬性結(jié)構(gòu):一對(duì)多關(guān)聯(lián),樹(shù)形
4. 圖形結(jié)構(gòu):多對(duì)多關(guān)聯(lián),網(wǎng)狀  

數(shù)據(jù)物理結(jié)構(gòu)指的是邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式(也稱(chēng)為存儲(chǔ)結(jié)構(gòu)).一般來(lái)說(shuō),一種數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)根據(jù)需要可以表示成多種存儲(chǔ)結(jié)構(gòu),常用的存儲(chǔ)結(jié)構(gòu)有順序存儲(chǔ),鏈?zhǔn)酱鎯?chǔ),索引存儲(chǔ)和哈希存儲(chǔ)等.

1. 順序存儲(chǔ):用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)集合的各個(gè)數(shù)據(jù)元素,可隨機(jī)存取,但增刪需要大批移動(dòng)
2. 鏈?zhǔn)酱鎯?chǔ):不要求連續(xù),每個(gè)節(jié)點(diǎn)都由數(shù)據(jù)域和指針域組成,占據(jù)額外空間,增刪快,查找慢需要遍歷
3. 索引存儲(chǔ):除建立存儲(chǔ)節(jié)點(diǎn)信息外,還建立附加的索引表來(lái)標(biāo)識(shí)節(jié)點(diǎn)的地址.檢索快,空間占用打
4. 哈希索引:將數(shù)據(jù)元素的存儲(chǔ)位置與關(guān)鍵碼之間建立確定對(duì)應(yīng)關(guān)系,檢索快,存在映射函數(shù)碰撞問(wèn)題

程序中常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)

1.數(shù)組: array 連續(xù)存儲(chǔ),線性結(jié)構(gòu),可根據(jù)偏移量隨機(jī)讀取,擴(kuò)容困難
2.棧: stack 線性存儲(chǔ),只允許一點(diǎn)操作,先進(jìn)后出,類(lèi)似水桶
3.隊(duì)列: queue 類(lèi)似棧,可以雙端操作,先進(jìn)先出,類(lèi)似水管
4.鏈表: linkedlist 鏈?zhǔn)酱鎯?chǔ),配備前后節(jié)點(diǎn)的指針,可以是雙向的
5.樹(shù): tree 典型的非線性結(jié)構(gòu),從唯一的根節(jié)點(diǎn)開(kāi)始,子節(jié)點(diǎn)單項(xiàng)執(zhí)行前驅(qū)(父節(jié)點(diǎn))
6.圖: graph 另一種非線性結(jié)構(gòu),由節(jié)點(diǎn)和關(guān)系組成,沒(méi)有根的概念,互相之間存在關(guān)聯(lián)
7.堆: heap 特殊的樹(shù),特點(diǎn)是根節(jié)點(diǎn)的值是所有節(jié)點(diǎn)中最小的或者最大的,且子樹(shù)也是堆
8.散列表: hash 源自于散列函數(shù),將值做一個(gè)函數(shù)式映射,映射的輸出作為存儲(chǔ)的地址

1.1.2 算法

算法指的是基于存儲(chǔ)結(jié)構(gòu)下,對(duì)數(shù)據(jù)如何有效的操作,采用什么方式可以更有效的處理數(shù)據(jù),提高數(shù)據(jù)運(yùn)行效率.數(shù)據(jù)的運(yùn)算是定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上,但運(yùn)算的具體實(shí)現(xiàn)要在存儲(chǔ)結(jié)構(gòu)上進(jìn)行.一般設(shè)計(jì)的操作有以下幾種

1.檢索:在數(shù)據(jù)結(jié)構(gòu)里查找滿(mǎn)足一定條件的節(jié)點(diǎn)
2.插入:往數(shù)據(jù)結(jié)構(gòu)中增加新的節(jié)點(diǎn),一般有一點(diǎn)位置上的要求
3.刪除:把指定的節(jié)點(diǎn)從數(shù)據(jù)結(jié)構(gòu)中去掉,本身可能隱含有檢索的需求
4.更新:改變指定節(jié)點(diǎn)的一個(gè)或者多個(gè)字段的值,同樣隱含檢索
5.排序:把節(jié)點(diǎn)里的數(shù)據(jù),按某種指定的順序重新排序,例如遞增或遞減

1.2 復(fù)雜度

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

簡(jiǎn)單理解,為了某種運(yùn)算而花費(fèi)的時(shí)間,使用大寫(xiě)O表示.一般來(lái)說(shuō),時(shí)間是一個(gè)不太容易計(jì)量的維度,而為了計(jì)算時(shí)間復(fù)雜度,通常會(huì)估計(jì)算法的操作單元數(shù)量,而假定每個(gè)單元運(yùn)行的時(shí)間都是相同的.因此,總運(yùn)行時(shí)間和算法的操作單元數(shù)量一般來(lái)講成正比,最多相差一個(gè)常亮系數(shù).一般來(lái)講,常見(jiàn)的時(shí)間復(fù)雜度有以下幾種:
1.常數(shù)階:時(shí)間與數(shù)據(jù)規(guī)模無(wú)關(guān),如交換兩個(gè)變量值

int i=1,j=2,k
k=i;i=j;j=k;

2.線性階:時(shí)間和數(shù)據(jù)規(guī)模呈線性,可以理解為n的1次方,如單循環(huán)里的操作

for(i=1;i<=n;i++){
  do();
}

3.k次方階:執(zhí)行次數(shù)是數(shù)量的k次方,如多重循環(huán),以下為2次方階實(shí)例

for(i=1;i<=n;i++){
  for(j=1;j<=n;j++){
    do();
  }
}

4.指數(shù)階:隨著n的上升,運(yùn)算次數(shù)呈指數(shù)增長(zhǎng)

for(i=1;i<=2^n;i++){
  do();
}

5.對(duì)數(shù)階:執(zhí)行次數(shù)呈對(duì)數(shù)縮減,如下

for(i=1;i<=n;){
  i=2^i
  do();
}

6.線性對(duì)數(shù)階:在對(duì)數(shù)階的基礎(chǔ)上,進(jìn)行線性n倍乘積

for(i=1;i<=2^n;i++){
  for(j=1;j<=n;j++){
    do();
  }
}

1.2.2 空間復(fù)雜度

與時(shí)間復(fù)雜度類(lèi)似,空間復(fù)雜度是對(duì)一個(gè)算法在運(yùn)行過(guò)程中占用內(nèi)存空間大小的度量.一個(gè)程序執(zhí)行時(shí)除了需要存儲(chǔ)空間和存儲(chǔ)本身所使用的指令 常數(shù) 變量和輸入數(shù)據(jù)外,還需要一些對(duì)數(shù)據(jù)進(jìn)行操作的輔助空間.而空間復(fù)雜度主要指的是這部分空間的量級(jí)

• 固定空間:主要包括指令空間 常量 簡(jiǎn)單變量等所占的空間 這部分空間的大小與運(yùn)算的數(shù)據(jù)多少無(wú)關(guān),屬于靜態(tài)空間
• 可變空間:主要包括運(yùn)行期間動(dòng)態(tài)分配的臨時(shí)空間,以及遞歸棧所需的空間等.這部分的空間大小與算法有很大關(guān)系

同樣,空間復(fù)雜度也用大寫(xiě)O表示,相比時(shí)間復(fù)雜度場(chǎng)景相對(duì)簡(jiǎn)單,常見(jiàn)級(jí)別為和

1.2.3 類(lèi)比

對(duì)于一個(gè)算法,其時(shí)間復(fù)雜度和空間復(fù)雜度往往是相互影響的.時(shí)間復(fù)雜度低可能借助占用大的存儲(chǔ)空間來(lái)彌補(bǔ),反之,某個(gè)算法所占據(jù)的空間小,那可能就需要占用更多的運(yùn)算時(shí)間.兩者往往需要達(dá)到一種權(quán)衡
在特定環(huán)境下的業(yè)務(wù),還需要綜合考慮算法的各項(xiàng)性能,如使用頻率 數(shù)據(jù)量的大小 所用的開(kāi)發(fā)語(yǔ)言 運(yùn)行的機(jī)器系統(tǒng)等.兩者兼顧權(quán)衡利弊才能設(shè)計(jì)出最適合當(dāng)前場(chǎng)景的算法

1.3 算法思想

1.3.1 分而治之

把一個(gè)復(fù)雜的問(wèn)題分成兩個(gè)或更多的相同或相似的子問(wèn)題,再把子分體分成更小的子問(wèn)題,直到最后子問(wèn)題小到可以簡(jiǎn)單的直接求解,原問(wèn)題的解即子問(wèn)題的解的合并.這個(gè)技巧是很多高效算法的基礎(chǔ),如排序算法(快速排序,歸并排序),傅里葉變換,大數(shù)據(jù)的MR
分治法對(duì)問(wèn)題有一定的要求:

• 該問(wèn)題縮小到一定程度后,就可以輕松解決
• 問(wèn)題具有可拆解性,不是一團(tuán)無(wú)法拆分的亂麻
• 拆解后的答案具有可合并行,能組裝成最終結(jié)果
• 拆解的子問(wèn)題要相互獨(dú)立,互相之間不存在或者很少有依賴(lài)關(guān)系

1.3.2 動(dòng)態(tài)規(guī)劃

基本思想與分治法蕾西,也是將待求解的問(wèn)題分解為若干個(gè)子問(wèn)題,按照順序求解子問(wèn)題,前一子問(wèn)題的解,為后一個(gè)子問(wèn)題的求解提供了有用的信息.在求解任一子問(wèn)題時(shí),列出各種可能的局部解,通過(guò)決策保留那些有可能打到最優(yōu)的局部解,丟棄其他.依次解決各子問(wèn)題,最后一個(gè)子問(wèn)題就是初始問(wèn)題的解
與分治法最大的不同在于,分治法的思想是并發(fā),動(dòng)態(tài)規(guī)劃的思想是分布.該方法經(jīng)分解后得到的子問(wèn)題往往不是互相獨(dú)立的,其下一個(gè)子問(wèn)題的求解往往是建立在上一個(gè)子問(wèn)題的解的基礎(chǔ)上.動(dòng)態(tài)規(guī)劃算法同樣有一定的適用性場(chǎng)景要求:

• 最優(yōu)化解:拆解后的子問(wèn)題具備最優(yōu)化解,且該最優(yōu)化解與追蹤答案方向一致
• 流程向前,無(wú)后效性:上一問(wèn)題的解決方案一旦確定,狀態(tài)就確定,只會(huì)影響下一步,而不會(huì)反向影響
• 階段關(guān)聯(lián):上下階段不是獨(dú)立的,上一階段會(huì)對(duì)下一階段的行動(dòng)提供決策性指導(dǎo),這不是必須的,但是如果具備該特性,動(dòng)態(tài)規(guī)劃算法的意義才能更大的得到體現(xiàn)

1.3.3 貪心算法

同樣對(duì)問(wèn)題要求做出拆解,但是每一步,以當(dāng)前局部為目標(biāo),求得該局部的最優(yōu)解.那么最終問(wèn)題解決時(shí),得到完整的最優(yōu)解.也就是說(shuō),在對(duì)問(wèn)題求解時(shí),總是做出在當(dāng)前看來(lái)是最好的選擇,而不是從整體最優(yōu)上加以考慮.從這一角度講,該算法具有一定的場(chǎng)景局限性

• 要求問(wèn)題可拆解,并且拆解后每一步的狀態(tài)無(wú)后效性(與動(dòng)態(tài)規(guī)劃算法類(lèi)似)
• 要求問(wèn)題每一步的局部最優(yōu),與整體最優(yōu)解方向一致.至少會(huì)導(dǎo)向正確的主方向

1.3.4 回溯算法

回溯算法實(shí)際上是一個(gè)類(lèi)似枚舉的搜索嘗試過(guò)程.在每一步的問(wèn)題下,列舉可能的解決方式.選擇某個(gè)方案往深度探究,尋找問(wèn)題的解,當(dāng)發(fā)現(xiàn)已經(jīng)不滿(mǎn)足求解條件,或深度達(dá)到一定數(shù)量時(shí),就返回,嘗試別的路徑.回溯法一般適用于比較復(fù)雜的,規(guī)模較大的問(wèn)題.有"通用解題法"之稱(chēng)

• 問(wèn)題的解決方案具備可列舉性,數(shù)量有限
• 界定回溯點(diǎn)的深度.達(dá)到一定程度后,折返

1.3.5 分支界限

與回溯法類(lèi)似,也是一種在空間上枚舉尋找最優(yōu)解的方式.但是回溯法策略為深度優(yōu)先.分支法為廣度優(yōu)先.分支法一般找到所有相鄰節(jié)點(diǎn),先采取淘汰策略,拋棄不滿(mǎn)足約束條件的節(jié)點(diǎn),其余節(jié)點(diǎn)加入活節(jié)點(diǎn)表.然后從存活表中選擇一個(gè)節(jié)點(diǎn)作為下一個(gè)操作對(duì)象