版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
數(shù)據(jù)結(jié)構(gòu)算法整理
文章目錄
時間&空間復(fù)雜度
一般情況下,算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函
數(shù),用T(n)表示,若有某個輔助函數(shù)f(n),使得當(dāng)n趨近于無窮大時,
T(n)/f(n)的極限值為不等于零的常數(shù),則稱f(n)是T(n)的同數(shù)量級函數(shù)。
記作T(n)=O(f(n)),稱0(f(n))為算法的漸進(jìn)時間復(fù)雜度,簡稱時間復(fù)
雜度。
常見的時間復(fù)雜度有:常數(shù)階0(1),對數(shù)[logarithmic]階0(log2n),
線性階0(n),線性對數(shù)階0(nlog2n),平方階0(n2),立方階0(n3),k
次方階0(nk),指數(shù)階0(2n)。隨著問題規(guī)模n的不斷增大,上述時間復(fù)
雜度不斷增大,算法的執(zhí)行效率越低。
算法時間復(fù)雜度由小到大依次為:0(1)<O(log2n)[二分]V
0(n)<0(nlog2n)<0(n2)<0(n3)<???<0(2n)<
0(n!)0
求解算法的時間復(fù)雜度的具體步驟是:
找出算法中的基本語句;
算法中執(zhí)行次數(shù)最多的那條語句就是基本語句,通常是最內(nèi)層循環(huán)的
循環(huán)體。
計算基本語句的執(zhí)行次數(shù)的數(shù)量級;
只需計算基本語句執(zhí)行次數(shù)的數(shù)量級,這就意味著只要保證基本語句
執(zhí)行次數(shù)的函數(shù)中的最高次幕正確即可,可以忽略所有低次幕和最高次塞
的系數(shù)。這樣能夠簡化算法分析,并且使注意力集中在最重要的一點上:
增長率。
用大0記號表示算法的時間性能。
將基本語句執(zhí)行次數(shù)的數(shù)量級放入大0記號中。
空間復(fù)雜度比較常用的有:0(1)、o(n)、0(n2)
如果算法執(zhí)行所需要的臨時空間不隨著某個變量n的大小而變化,即
此算法空間復(fù)雜度為一個常量,可表示為0(1)
如果新建一個數(shù)組,這個數(shù)據(jù)占用的大小為n,雖然有循環(huán),但沒有
再分配新的空間,因此,空間復(fù)雜度主要看數(shù)組大小即可,即S(n)=0(n)o
數(shù)據(jù)結(jié)構(gòu)
線性與非線性
線性:數(shù)組(Array)、鏈表(LinkedList)、棧(Stack)、隊列(Queue)
非線形:多維數(shù)組、樹結(jié)構(gòu)、圖結(jié)構(gòu)
常見數(shù)據(jù)結(jié)構(gòu)
稀疏數(shù)組
場景:解壓縮
當(dāng)一個數(shù)組中大部分元素為0,或者為同一個值的數(shù)組時,可以使用
稀疏數(shù)組來保存。
處理方法是:
第一行記錄數(shù)組一共有幾行幾列和不同值的個數(shù);而后記錄每行不同
值的位置與實際值
環(huán)形隊列
通過取模的方式實現(xiàn)。尾索引的下一個為頭索引時表示隊列滿
雙向鏈表
prev,next
單向環(huán)形鏈表
(約瑟夫環(huán))
先創(chuàng)建一個節(jié)點,讓first指向自己,形成環(huán)形;后面每創(chuàng)建一個新
節(jié)點,就將其加入到鏈表中(first.next=new;new.next=first)o
棧
先進(jìn)后出結(jié)構(gòu),入棧push(top++),出棧pop(top-)[poll取空不
報錯]
常見排序算法
插入排序
直接插入排序
希爾排序
選擇排序
簡單選擇排序
堆排序
交換排序
冒泡排序
快速排序
歸并排序
基數(shù)排序
內(nèi)排序:所有排序操作都在內(nèi)存完成
外排序:由于數(shù)據(jù)太大,需要把數(shù)據(jù)放在磁盤,通過磁盤和內(nèi)存的數(shù)
據(jù)傳輸才能進(jìn)行
交換排序-冒泡排序
重復(fù)地走訪過要排序的數(shù)列,一次比較兩個元素,如果它們的順序錯
誤就把它們交換過來。
publicvoidmaopao({
int[]arr={0,-1,4,-2,9,5};
inttemp;
for(inti=0;i<arr.length-1;i++){
for(intj=0;j<arr.length-1-i;j++){〃趟
數(shù)是lenT-i
if(arr[j+1]<arr[j]){
temp=arr[j+1];
arr[j+1]=arr
arr[j]=temp;
}
)
)
System,out.printin(Arrays.toString(arr));
)o
交換排序?快速排序
通過一趟排序?qū)⒋庞涗浄指舫瑟毩⒌膬刹糠?,其中一部分記錄的關(guān)
鍵字均比另一部分的關(guān)鍵字小,則可分別對這兩部分記錄繼續(xù)進(jìn)行排序,
以達(dá)到整個序列有序。
publicvoidquicksort({
int[]arr={0,-1,4,-2,9,5,-3,4,8,7};
sort(arr,0,arr.length-1);
System,out.printin(Arrays.toString(arr));
)
privatevoidsort(int[]arr,intleft,intright){
int1=left;〃左下標(biāo)
intr=right;〃右下標(biāo)
intpivot=arr[(left+right)/2];//中軸值
inttemp=0;
while(1<r){
while(arr[1]<pivot){〃在pivot左邊找
1+=1;
)
while(arr[r]>pivot){〃在pivot右邊找
r-=1;
)
if(1>=r){
break;
}
//交換
temp=arr[1];
arr[1]=arr[r];
arr[r]=temp;
if(arr[1]==pivot){〃前移
r-=1;
if(arr[r]==pivot){〃后移
1+=1;
)
if(1==r){
1+=1;
r-=1;
}
if(left<r){〃向左遞歸
sort(arr,left,r);
)
if(right>1){〃向右遞歸
sort(arr,1,right);
)
)o
選擇排序
首先在未排序的序列中找到最小(大)元素,存放到排序序列的起始
位置;再從剩余未排序元素中繼續(xù)尋找最小(大)元素,然后放到已排序
序列的末尾。
publicvoidchooseSort({
int[]arr={0,-1,4,-2,9,5};
intmini,temp;
for(inti=0;i<arr.length-1;i++){
mini=i;
for(intj=i+1;j<arr.length;j++){
if(arr[j]<arr[mini]){〃找到最小(或最大)
mini=j;
}
}
temp=arr[i];
arr[i]=arr[mini];
arr[mini]=temp;
)
System,out.printin(Arrays.toString(arr));
)o
堆排序
也是一種選擇排序,也是一種完全二叉樹:每個節(jié)點的值都大于或等
于其左右孩子節(jié)點的值,稱為大頂堆;小于等于稱為小頂堆。
插入排序
通過構(gòu)建有序序列,對于未排序數(shù)據(jù),在已排序序列中從后向前掃描,
找到相應(yīng)位置并插入。
publicvoidinsertSort({
int[]arr={0,-1,4,一2,9,5};
intlasti,curr;
for(inti=1;i<arr.length;i++){
lasti=i-1;〃上一個索引
curr=arr[i];
while(lasti>=0&&arr[lasti]>curr){
arr[lasti+1]=arr[lasti];
lasti一;
)
arr[lasti+1]=curr;
}
System,out.printin(Arrays.toString(arr));
}o
其他:希爾排序,縮小增量排序
歸并排序
將多個有序的子序列合并,得到完全有序的序列,即先使每個子序列
有序,再使子序列段間有序。
publicvoidmergeSortTest({
int[]arr={8,4,5,7,1,3,6,2};
int[]temp=newint[arr.length];〃額外空間排序
mergeSort(arr,0,arr.length-1,temp);
System,out.printin(Arrays.toString(arr));
)
privatevoidmergeSort(int[]arr,intleft,intright,int[]
temp){
if(left<right){
intmiddle=(left+right)/2;
mergeSort(arr,left,middle,temp);〃向左遞歸分解
mergeSort(arr,middle+1,right,temp);〃向右遞歸
分解
merge(arr,left,middle,right,temp);〃再合并
)
)
publicvoidmerge(int[]arr,intleft,intmiddle,intright,
int[]temp){
inti=left;〃左邊初始序列索引
intj=middle+1;〃右邊初始序列索引
intt=0;〃指向temp數(shù)組的當(dāng)前索引
while(i<=middle&&j<=right){
if(arr[i]<=arr[j]){
temp[t]=arr[i];
t+=1;
i+=1;
}else{
temp[t]=arr[j];
t+=1;
j+=1;
)
}
〃剩余元素填充
while(i<=middle){
temp[t]=arr[i];
t+=1;
i+=1;
while(j<=right){
temp[t]=arr[j];
t+=1;
j+=1;
)
//將temp數(shù)組拷貝到arr
t=0;
inttempLeft=left;
while(tempLeft<=right){
arr[tempLeft]=temp[t];
t+=1;
tempLeft+=1;
}
}o
基數(shù)排序
桶排序一種,將整數(shù)按照位數(shù)切割,然后按每個位數(shù)分別比較(消耗
存儲,容易OOM)
案例一-文件修改時間排序
案例二?文件名稱排序
常見查找算法
二分查找
publicstaticvoidmain(String[]args){
int[]arr=newint[]{1,4,5,7,8,12,45,67,99,
105};
System,out.printin(biSearch(arr,99));
)
publicstaticintbiSearch(int[]arr,intnum){
intstart=0;
intend=arr.length-1;
intmid;
while(start<=end){
System,out.printing'*");
mid=(start+end)/2;
if(arr[mid]==num){
returnmid+1;
}elseif(arr[mid]>num){//向左查找
end=mid-1;
}else{//向右查找
start=mid+1;
)
)
return-1;
}
publicstaticintbiSearch2(int[]arr,intstart,intend,
intnum){
if(start>end){
return-1;
)
intmid=(start+end)/2;
intmidVai=arr[mid];
if(midVai==num){
returnmid;
}elseif(midVai>num){//向左查找
returnbiSearch2(arr,start,end-1,num);
}else{//向右查找
returnbiSearch2(arr,start+1,end,num);
//查找多個值的情況。
插值查找
類似于二分,不同的是每次從自適應(yīng)mid處開始查找,適用于連續(xù)且
量大的數(shù)據(jù)
公式:intmid=left+(right-left)*(findVal-arr[left])
/(arr[right]-arr[left])
注意需要判斷findVal過大或過小越界的情況。
樹結(jié)構(gòu)
數(shù)組、鏈表和二叉樹的優(yōu)缺點略
二叉樹
每個節(jié)點最有只有兩個子節(jié)點(左節(jié)點、右節(jié)點)
滿二叉樹、完全二叉樹
前序遍歷:先輸出父節(jié)點,再遍歷左子樹和右子樹
中序遍歷:先遍歷左子樹,再輸出父節(jié)點,再遍歷右子樹
后序遍歷:先遍歷左子樹,再遍歷右子樹,再輸出父節(jié)點
二叉排序樹
左邊比根節(jié)點小,右邊比根節(jié)點大
二叉排序樹既可以保證數(shù)據(jù)的檢索速度,同時也可以保證增刪改的速
度
問題:極端情況,插入有序會退化成鏈表
publicvoidinsert(Treetree,intvalue){
if(tree.getValue(==0){
tree.setValue(value);
}elseif(tree.getValue(<value){
if(tree.getRight(==null){
tree.setRight(newTree();
)
insert(tree.getRight(,value);
}elseif(tree.getValue(>value){
if(tree.getLeft(==null){
tree.setLeft(newTree();
}
insert(tree.getLeft(,value);
)
}o
紅黑樹
平衡二叉樹AVL的一種,降低樹的高度,樹高最大最小之差不超過1,
實現(xiàn)方式:旋轉(zhuǎn)(左、右、雙旋轉(zhuǎn)(左+右))。Java中的TreeSet底層用
的就是紅黑樹。
左旋轉(zhuǎn):
NodenewNode=newNode(value);
newNode.left=left;
newNode.right=right,left;
value=right.value;
right=right.right;
left=newNode;0
B樹
B+樹
在B樹的基礎(chǔ)上改造,它的數(shù)據(jù)都在葉子節(jié)點,同時葉子節(jié)點之間還
加了指針形成鏈表
由于所有數(shù)據(jù)都在葉子結(jié)點,不用跨層,同時由于有鏈表結(jié)構(gòu),只需
要找到首尾,通過鏈表就能把所有數(shù)據(jù)取出來了
一般用于數(shù)據(jù)庫索引(如果只取一條數(shù)據(jù),Hash快)。
赫夫曼樹
赫(哈Huffman)夫曼樹帶權(quán)路徑長度最小的二叉樹,也稱最優(yōu)二叉
樹
創(chuàng)建一個赫夫曼樹
應(yīng)用:通訊領(lǐng)域信息傳輸、文件壓縮解壓,赫夫曼編碼(按照各個字
符出現(xiàn)的次數(shù)進(jìn)行編碼)
遞歸與分治
遞歸
當(dāng)程序執(zhí)行到一個方法時,就會獨立開辟一個空間(棧),每個空間
中的局部變量也是獨立的。
注意遞歸調(diào)用處前后代碼的執(zhí)行順序
publicstaticvoidshow(intn){
System,out.printin(z/nl:"+n);//10->2
if(n>2){
show(n-1);
}
System,out.println(,,n2:"+n);〃2->10
)o
分治
待解決復(fù)雜的問題能夠簡化為幾個若干個小規(guī)模相同的問題,然后逐
步劃分,達(dá)到易于解決的程度。應(yīng)用:階乘、斐波納契數(shù)列、漢諾塔問題、
棋盤覆蓋、找出偽幣、求最值
案例一?漢諾塔
publicstaticvoidmain({
move(5,"A柱〃,〃B柱”,〃C柱〃);
)
publicstaticvoidmove(intnum,Stringa,Stringb,String
c){
if(num==1){
disPaly(num,a,c);
}else{
move(num-1,a,c,b);
disPaly(num,a,c);
move(num-1,b,a,c);
)
)
publicstaticvoiddisPaly(intnum,Stringsi,Strings2){
System,out.printin("第"+num+”個塔從"+si+"到"+
s2);
}。
案例二?走迷宮
publicstaticvoidmain(String[]args){
int[][]map={
{1,1,1,1,1,1,1,1,1},
(1,0,0,0,0,0,0,0,1},
{1,1,1,1,0,1,1,1,1),
{1,1,0,0,0,0,0,1,1},
{1,0,0,1,0,1,1,1,1},
{1,o,1,1,0,1,1,1,1},
{1,o,0,1,1,1,1,1,1},
{1,o,0,0,1,1,1,1,1},
{1,1,1,o,1,1,1,1,1},
{1,1,1,0,0,0,0,0,1},
(1,1,1,1,1,1,1,1,1}
);
System,out.printin("原來的地圖11*9");
for(inti=0;i<11;i++){
for(intj=0;j<9;j++){
System,out.print(map[i][j]+“");
System,out.printin(;
//1,1是起點9,7是終點
setWay(map,1,1);
System,out.printin("走過的地圖”);
for(inti=0;i<11;i++){
for(intj=0;j<9;j++){
if(map[i][j]==2){
System,out.format(,z\33[32;lm,/+map[i][j]+
“\33[0m〃);
}else{
System,out.print(map[i][j]+"");
}
)
System,out.printin(;
}
}
//0-還沒走1-不可以走2-可以走3-走過不行
publicstaticbooleansetWay(int[][]map,intx,inty){
if(map[9][7]==2){
returntrue;
else{
if(map[x][y]==0){
map[x][y]=2;
if(setWay(map,x+1,y)){〃下
returntrue;
}elseif(setWay(map,x,y+1)){//右
returntrue;
}elseif(setWay(map,x-1,y)){〃上
returntrue;
}elseif(setWay(map,x,y-1)){〃左
returntrue;
}else{
map[x][y]=3;
returnfalse;
}else{
returnfalse;
)o
動態(tài)規(guī)劃
動態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問題。在這類問題中,
可能會有許多可行解。每一個解都對應(yīng)于一個值,我們希望找到具有最優(yōu)
值的解,使用填表的方式。
與分治法不同的是,分解得到的子問題是非獨立的,即下一個子階段
的求解是建立在上一個子階段的解的基礎(chǔ)上。
案例一?有n級臺階,一個人每次上一級或者兩級,問有多少種走完
n級臺階的方法。
publicstaticint[]steps=newint[11];
publicstaticvoidmain({
steps[10]=calStep(10);
for(inti=0;i<steps,length;i++){
System,out.print(steps[i]+"");
}
System,out.printin(;
System,out.printIn(steps[10]);
)
privatestaticintcalStep(intn){
if(n==1||n==2){
returnn;
)
if(steps[n-1]==0){
steps[n-1]calStep(n-1);
if(steps[n-2]==0){
steps[n-2]=calStep(n-2);
returnsteps[n-1]+steps[n-2];
)o
案例二-給定一個矩陣,從左上角開始每次只能向右走或者向下走,
最后達(dá)到右下角的位置,路徑中所有數(shù)字累加起來就是路徑和,返回所有
路徑的最小路徑和
publicvoidstep({
int[][]arr={
{4,1,5,3),
{3,2,7,7),
{6,5,2,8},
[8,9,4,5)
);
intresult=minSteps(arr);
System,out.printin(,,result=/,+result);
)
privatestaticintminSteps(int[][]arr){
introw=arr.length;
intcol=arr[0].length;
int[][]steps=newint[row][col];
steps[0][0]=arr[0][0];
for(inti=1;i<row;i++){//列+,從上到下
steps[i][0]=steps[i-1][0]+arr[i][0];
)
for(intj=1;j<col;j++){//行+,從左到右
steps[0][j]=steps[0][j-1]+arr[0][j];
}
for(inti=1;i<row;i++){
for(intj=1;j<col;j++){
steps[i][j]=Math,min(steps[i-1][j],
steps[i][j-1])+arr[i][j];
)
}
/*for(inti=0;i<steps.length;i++){
for(inti1=0;il<steps,length;i1++){
System,out.print(steps[i][il]+"");
)
System,out.print("\n");
}*/
returnsteps[row-1][col-1];
}
〃優(yōu)化解法
publicstaticintminSteps2(int[][]arr){
intcol=arr[0].length;
int[]steps=newint[col];
steps[0]=arr[0][0];
for(inti=1;i<col;i++){
steps[i]=steps[i-1]+arr[0][i];〃第一行
for(inti=1;i<arr.length;i++){
steps[0]=arr[i][0]+steps[0];〃每一行的最左邊
for(intj=1;j<col;j++){
steps[j]=Math,min(steps[j-1]+arr[i][j],
steps[j]+arr[i][j]);
}
)
System,out.printin(Arrays.toString(steps));
returnsteps[col-1];
}o
貪心算法
在每一
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 主任醫(yī)師述職報告范文
- 人教版小學(xué)五年級下冊信息技術(shù)教案
- 高考語文復(fù)習(xí)- 高考語文文學(xué)類文本閱讀8 小說(小說“6+1”答題法)(講義)
- 2024-2025學(xué)年初中數(shù)學(xué)九年級下冊人教版(2024)教學(xué)設(shè)計合集
- 2024年秋季大班教師個人工作計劃
- 使用林地可行性報告三篇
- 2024年08月金華事業(yè)單位公開招聘金華市農(nóng)產(chǎn)品質(zhì)量安全中心公開招聘1人檢測人員筆試歷年典型考點解題思路附帶答案詳解
- 2024年3月上半年四川成都市招考聘用中小學(xué)教師1202人筆試歷年典型考點解題思路附帶答案詳解
- 用心傾聽感受生活
- 初中模擬試卷:理論測驗篇
- 民航英語1(山東聯(lián)盟)智慧樹知到課后章節(jié)答案2023年下青島恒星科技學(xué)院
- 消防安全重點單位標(biāo)準(zhǔn)化管理操作手冊
- 2023年北京市通州區(qū)城管協(xié)管員招聘筆試題庫及答案解析
- 思想道德與法治 第三章
- 中國石油大學(xué)(北京)遠(yuǎn)程教育報名登記表34
- 土方運輸小票(共2頁)
- 超聲波療法PPT課件
- 26個英文字母經(jīng)典手寫體描紅(精編版)
- 呼叫中心KPI指標(biāo)資料
- 《整式的加減》競賽題
- 《管寧割席》
評論
0/150
提交評論