Java舉例講解分治算法思想
分治算法
什么是分治算法
顧名思義就是分而治之,分治法可以用來解決各種問題,是一種將復(fù)雜難解的問題分割成規(guī)模和結(jié)構(gòu)相同或者相似的子問題,通過對簡單子問題的求解而達(dá)到對原問題的求解目的的算法設(shè)計方法,在求解一個復(fù)雜問題時可以將其分解成若干個子問題,子問題還可以進(jìn)一步分解成更小的子子問題,直到解決的子問題是一些基本的問題,并且求解方法是已知的,可以直接求解為止。分而治之的策略不但能夠使原本復(fù)雜的問題變得更加清晰,而且能夠?qū)栴}的規(guī)??s小而降低問題求解的難度。
分治算法的思想
對于一個規(guī)模較大的問題,可以將這個規(guī)模較大的問題分解為n個規(guī)模較小的相互獨(dú)立且與原問題結(jié)構(gòu)相同的子問題進(jìn)行求解。首先通過遞歸來解決這些子問題,然后對子問題的解進(jìn)行合并得到原問題的解,這中求解問題的思路就是分治法。
簡單可以理解為
首先將原問題分解為若干個子問題
各子問題的結(jié)構(gòu)基本相似,規(guī)?;鞠喈?dāng)
遞歸使分治的工具
- 遞歸調(diào)用:問題和子問題的分解
- 遞歸約束:對子問題的解進(jìn)行合并
分治法四大基本特征
- 原問題的規(guī)??s小到一定程度時可以很容易的被求解。
- 原問題可以分解成若干個規(guī)模較小的同構(gòu)子問題。這是使用分治法的前提,這個特征和遞歸的思想差不多,滿足這個特征的問題通常稱這個問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。
- 各問題的解可以合并為原問題的解
- 原問題所分出的各個子問題之間是相互獨(dú)立的,即子問題之間不包含公共的子問題,
分治法求解問題的三個基本步驟
- 分解(遞歸調(diào)用):將原問題分解為若干個相互獨(dú)立,規(guī)模較小且與原問題形式相同的一系列子問題。在使用分治算法時,最好使各子問題的規(guī)模大致相同。
- 解決(對子問題求解):如果子問題的規(guī)模小到可以直接被解決則直接解決,否則需要遞歸求解各個子問題。
- 合并(遞歸約束):將各個子問題的結(jié)果合并成原問題的解,有些問題的合并方法比較明顯,有些問題的合并方法比較復(fù)雜,或者存在多種合并方案,有些問題的合并方案并不明顯需要具體問題具體分析。
分治算法解決問題過程的偽代碼
divide-and-conquer(p)//閥值
{
if(|p|<n0)adhoc(p);//如果問題可以直接求解,就直接求解。|p|代表問題的規(guī)模
divide p into amaller subinstances P1,P2,P3......Pk;//將原問題分解成k個規(guī)模較小的子問題,且這些子問題的規(guī)模相當(dāng)結(jié)構(gòu)相似
for(i=1;i<=k;i++)
yi=divide-and-conquer(p)//遞歸求解各個子問題Pi,若分解的子問題還可以分解成若干個子子問題,就再對子問題進(jìn)行分解
return merge(y1,y2,y3......yk)//將子問題的解合并成原問題的解
}
關(guān)于分治算法的舉例
歸并排序
歸并排序算法是用分治策略實現(xiàn)對規(guī)模為n的記錄序列進(jìn)行排序的算法,基本思想是:待排序記錄分成大小大致相同的兩個或多個子集合,分別對子集合進(jìn)行排序,最終將兩個排序號的子集合合并成所要求的排序好的集合。
package 算法設(shè)計與分析; public class 歸并排序 { //arr是存放原始元素的數(shù)組,left數(shù)組arr的最左邊,left是數(shù)組的最右邊,mid是劃分的終點(diǎn),數(shù)組tmp是一個臨時數(shù)組,就是一個輔助存儲空間 public static void main(String[] args) { int[] arr = {49,38,65,97,76,13,27}; int[] tmp = new int[arr.length]; //新建一個臨時數(shù)組存放,相當(dāng)于是一個輔助空間 mergeSort(arr,0,arr.length-1,tmp); for(int i=0;i<arr.length;i++){ System.out.print(arr[i]+" "); } } public static void merge(int[] arr,int left,int mid,int right,int[] tmp){ int i = 0; int j = left,k = mid+1; //左邊序列和右邊序列起始索引 while(j <= mid && k <= right){ if(arr[j] <= arr[k]){ tmp[i++] = arr[j++]; }else{ tmp[i++] = arr[k++]; } } //若左邊序列還有剩余,則將其全部拷貝進(jìn)tmp[]中 while(j <= mid){ tmp[i++] = arr[j++]; } while(k <= right){ tmp[i++] = arr[k++]; } for(int t=0;t<i;t++){ arr[left+t] = tmp[t]; } } public static void mergeSort(int[] arr,int left,int right,int[] tmp){ if(left<right){ int mid = (left+right)/2; mergeSort(arr,left,mid,tmp); //對左邊序列進(jìn)行歸并排序 mergeSort(arr,mid+1,right,tmp); //對右邊序列進(jìn)行歸并排序 merge(arr,left,mid,right,tmp); //合并兩個有序序列,相當(dāng)于用tmp覆蓋原來的arr } } }
基本步驟
- 劃分中點(diǎn)mid;
- 分別對左右子區(qū)間歸并排序,歸并的結(jié)果(是一個有序序列)存放在數(shù)組tmp中,tmp是一個臨時數(shù)組,相當(dāng)于一個輔助存儲空間;
- 用tmp去覆蓋原來的數(shù)組arr。
快速排序
快速排序又稱為交換排序,是冒泡排序的一種,在快速排序中,記錄的比較和交換是從兩端向中間進(jìn)行的,關(guān)鍵字值較大的記錄一次就能交換到后面單元,關(guān)鍵字值小的記錄一次就能交換到前面單元,記錄每次移動的距離較大,因而總的比較和移動次數(shù)較少。
思想:把最左邊的元素作為主元,數(shù)組一左一右兩個指針進(jìn)行掃描,左邊的指針直到找到一個元素比主元大時,便停止左移,右邊的指針向左移動,直到找到一個不大于主元的元素,交換兩個指針?biāo)赶虻脑亍?/p>
注意:這種排序要在左邊設(shè)置一個較大的值作為哨兵,防止左指針在右移的過程中移出序列之外。
package 算法設(shè)計與分析; public class 快速排序 { public static void quickSort(int[] arr,int left,int right){ int i,j,temp,t; if(left>right){ return; } i=left; j=right; //temp就是基準(zhǔn)位,就是主元,將數(shù)組中的第一個元素作為主元 temp = arr[left]; while (i<j) { //先看右邊,依次往左遞減 while (temp<=arr[j]&&i<j) { j--; } //再看左邊,依次往右遞增 while (temp>=arr[i]&&i<j) { i++; } //如果滿足條件則交換 if (i<j) { t = arr[j]; arr[j] = arr[i]; arr[i] = t; } } //最后將基準(zhǔn)為與i和j相等位置的數(shù)字交換 arr[left] = arr[i]; arr[i] = temp; //遞歸調(diào)用左半數(shù)組 quickSort(arr, left, j-1); //遞歸調(diào)用右半數(shù)組 quickSort(arr, j+1, right); } public static void main(String[] args){ int[] arr = {72,26,57,88,42,80,72,48,60,}; quickSort(arr, 0, arr.length-1); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i]+ " "); } } }
二分搜索算法
在一個表中搜索確定一個關(guān)鍵字值為給定的元素,若在表中存在這樣的元素,則搜索成功,搜索結(jié)果可以返回整個數(shù)據(jù)的元素,也可以指示該元素在表中的位置,若表中不存在關(guān)鍵字值的元素,則搜索失敗。
package 算法設(shè)計與分析; //用遞歸的方法解決二分搜索問題 public class 二分查找 { public static void main(String[] args) { int[] arr = {-7,-2,0,15,27,54,80,88,102}; //想要查找的元素 int key = 80; //對查找到的元素進(jìn)行定位 int position = Search(arr,key,0,arr.length - 1); if(position == -1){ System.out.println("查找的是"+key+",序列中沒有該數(shù)!"); }else{ System.out.println("查找的是"+key+",找到位置為:"+position); } } public static int Search(int[] arr,int key,int left,int right){ if(key < arr[left] &&key > arr[right] &&left > right){ return -1; } int middle = (left + right) / 2; //初始中間位置 if(arr[middle] > key){ //比關(guān)鍵字大則關(guān)鍵字在左區(qū)域 return Search(arr, key, left, middle - 1); }else if(arr[middle] < key){ //比關(guān)鍵字小則關(guān)鍵字在右區(qū)域 return Search(arr, key, middle + 1, right); }else { return middle; } } }
小結(jié)
以上就是針對分治算法的詳細(xì)分析,分治算法在我們解決問題的過程中可以使我們的問題變得簡單化,降低時間復(fù)雜度,利用分治法解決問題比較穩(wěn)定。
到此這篇關(guān)于Java舉例講解分治算法思想的文章就介紹到這了,更多相關(guān)Java分治算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
SpringBoot結(jié)合Redis實現(xiàn)緩存管理功能
本篇文章主要介紹spring boot緩存管理機(jī)制及相關(guān)概念,以及如何結(jié)合Redis實現(xiàn)緩存管理,文中通過代碼示例給大家介紹的非常詳細(xì),具有一定的參考價值,需要的朋友可以參考下2024-01-01Spring MVC學(xué)習(xí)之DispatcherServlet請求處理詳析
這篇文章主要給大家介紹了關(guān)于Spring MVC學(xué)習(xí)教程之DispatcherServlet請求處理的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧2018-11-11Java實現(xiàn)數(shù)字轉(zhuǎn)成英文的方法
這篇文章主要介紹了Java實現(xiàn)數(shù)字轉(zhuǎn)成英文的方法,涉及java數(shù)組與字符串的相關(guān)操作技巧,需要的朋友可以參考下2015-05-05Java 實戰(zhàn)項目錘煉之網(wǎng)上圖書館管理系統(tǒng)的實現(xiàn)流程
讀萬卷書不如行萬里路,只學(xué)書上的理論是遠(yuǎn)遠(yuǎn)不夠的,只有在實戰(zhàn)中才能獲得能力的提升,本篇文章手把手帶你用Java+jsp+servlet+mysql+ajax實現(xiàn)一個網(wǎng)上圖書館管理系統(tǒng),大家可以在過程中查缺補(bǔ)漏,提升水平2021-11-11使用java實現(xiàn)備份和恢復(fù)SQLServer表數(shù)據(jù)
這篇文章主要為大家詳細(xì)介紹了如何使用java實現(xiàn)備份和恢復(fù)SQLServer表數(shù)據(jù),文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2024-01-01Mybatis Generator Plugin悲觀鎖實現(xiàn)示例
本文將從悲觀鎖為例,讓你快速了解如何實現(xiàn)Mybatis Generator Plugin。文中通過示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下2021-09-09Java上傳文件到服務(wù)器指定文件夾實現(xiàn)過程圖解
這篇文章主要介紹了Java上傳文件到服務(wù)器指定文件夾實現(xiàn)過程圖解,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-08-08