欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java舉例講解分治算法思想

 更新時間:2022年04月29日 10:32:43   作者:LNORA  
分治算法的基本思想是將一個規(guī)模為N的問題分解為K個規(guī)模較小的子問題,這些子問題相互獨(dú)立且與原問題性質(zhì)相同。求出子問題的解,就可得到原問題的解,本篇文章我們就用分治算法來實現(xiàn)歸并排序快速排序以及二分搜索算法

分治算法

什么是分治算法

顧名思義就是分而治之,分治法可以用來解決各種問題,是一種將復(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)緩存管理功能

    SpringBoot結(jié)合Redis實現(xiàn)緩存管理功能

    本篇文章主要介紹spring boot緩存管理機(jī)制及相關(guān)概念,以及如何結(jié)合Redis實現(xiàn)緩存管理,文中通過代碼示例給大家介紹的非常詳細(xì),具有一定的參考價值,需要的朋友可以參考下
    2024-01-01
  • Spring MVC學(xué)習(xí)之DispatcherServlet請求處理詳析

    Spring MVC學(xué)習(xí)之DispatcherServlet請求處理詳析

    這篇文章主要給大家介紹了關(guān)于Spring MVC學(xué)習(xí)教程之DispatcherServlet請求處理的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧
    2018-11-11
  • Java實現(xiàn)數(shù)字轉(zhuǎn)成英文的方法

    Java實現(xiàn)數(shù)字轉(zhuǎn)成英文的方法

    這篇文章主要介紹了Java實現(xiàn)數(shù)字轉(zhuǎn)成英文的方法,涉及java數(shù)組與字符串的相關(guān)操作技巧,需要的朋友可以參考下
    2015-05-05
  • Java 實戰(zhàn)項目錘煉之網(wǎng)上圖書館管理系統(tǒng)的實現(xiàn)流程

    Java 實戰(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ù)

    使用java實現(xiàn)備份和恢復(fù)SQLServer表數(shù)據(jù)

    這篇文章主要為大家詳細(xì)介紹了如何使用java實現(xiàn)備份和恢復(fù)SQLServer表數(shù)據(jù),文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下
    2024-01-01
  • Java中JWT的使用的詳細(xì)教程

    Java中JWT的使用的詳細(xì)教程

    JWT的本質(zhì)就是一個字符串,它是將用戶信息保存到一個Json字符串中,然后進(jìn)行編碼后得到一個JWT token,并且這個JWT token帶有簽名信息,接收后可以校驗是否被篡改,所以可以用于在各方之間安全地將信息作為Json對象傳輸,本文介紹了Java中JWT的使用,需要的朋友可以參考下
    2023-02-02
  • Java排序算法中的快速排序算法實現(xiàn)

    Java排序算法中的快速排序算法實現(xiàn)

    這篇文章主要介紹了Java排序算法中的快速排序算法實現(xiàn),通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分,其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小,然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序,需要的朋友可以參考下
    2023-12-12
  • SpringBoot Controller中的常用注解

    SpringBoot Controller中的常用注解

    這篇文章主要介紹了SpringBoot Controller中的常用注解,文章圍繞主題展開詳細(xì)的內(nèi)容介紹,具有有一定的參考價值,需要的小伙伴可以參考一下
    2022-09-09
  • Mybatis Generator Plugin悲觀鎖實現(xiàn)示例

    Mybatis Generator Plugin悲觀鎖實現(xiàn)示例

    本文將從悲觀鎖為例,讓你快速了解如何實現(xiàn)Mybatis Generator Plugin。文中通過示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2021-09-09
  • Java上傳文件到服務(wù)器指定文件夾實現(xiàn)過程圖解

    Java上傳文件到服務(wù)器指定文件夾實現(xiàn)過程圖解

    這篇文章主要介紹了Java上傳文件到服務(wù)器指定文件夾實現(xiàn)過程圖解,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下
    2020-08-08

最新評論