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

詳解Java實(shí)現(xiàn)分治算法

 更新時(shí)間:2021年06月16日 10:15:52   作者:bigsai  
分治算法(divide and conquer)是五大常用算法(分治算法、動(dòng)態(tài)規(guī)劃算法、貪心算法、回溯法、分治界限法)之一,很多人在平時(shí)學(xué)習(xí)中可能只是知道分治算法,但是可能并沒有系統(tǒng)的學(xué)習(xí)分治算法,本篇就帶你較為全面的去認(rèn)識和了解分治算法

一、前言

在學(xué)習(xí)分治算法之前,問你一個(gè)問題,相信大家小時(shí)候都有存錢罐的經(jīng)歷,父母親人如果給錢都會(huì)往自己的寶藏中存錢,我們每隔一段時(shí)間都會(huì)清點(diǎn)清點(diǎn)錢。但是一堆錢讓你處理起來你可能覺得很復(fù)雜,因?yàn)閿?shù)據(jù)相對于大腦有點(diǎn)龐大了,并且很容易算錯(cuò),你可能會(huì)將它先分成幾個(gè)小份算,然后再疊加起來計(jì)算總和就獲得這堆錢的總數(shù)了

當(dāng)然如果你覺得各個(gè)部分錢數(shù)量還是太大,你依然可以進(jìn)行劃分然后合并,我們之所以這么多是因?yàn)椋?/p>

  • 計(jì)算每個(gè)小堆錢的方式和計(jì)算最大堆錢的方式是相同的(區(qū)別在于體量上)
  • 然后大堆錢總和其實(shí)就是小堆錢結(jié)果之和。這樣其實(shí)就有一種分治的思想。

二、分治算法介紹

分治算法是用了分治思想的一種算法,什么是分治?

分治,字面上的解釋是“分而治之”,就是把一個(gè)復(fù)雜的問題分成兩個(gè)或更多的相同或相似的子問題,再把子問題分成更小的子問題……直到最后子問題可以簡單的直接求解,原問題的解即子問題的解的合并。在計(jì)算機(jī)科學(xué)中,分治法就是運(yùn)用分治思想的一種很重要的算法。分治法是很多高效算法的基礎(chǔ),如排序算法(快速排序,歸并排序),傅立葉變換(快速傅立葉變換)等等。

將父問題分解為子問題同等方式求解,這和遞歸的概念很吻合,所以在分治算法通常以遞歸的方式實(shí)現(xiàn)(當(dāng)然也有非遞歸的實(shí)現(xiàn)方式)。分治算法的描述從字面上也很容易理解,分、治其實(shí)還有個(gè)合并的過程:

  • 分(Divide):遞歸解決較小的問題(到終止層或者可以解決的時(shí)候停下)
  • 治(Conquer):遞歸求解,如果問題夠小直接求解。
  • 合并(Combine):將子問題的解構(gòu)建父類問題

一般分治算法在正文中分解為兩個(gè)即以上的遞歸調(diào)用,并且子類問題一般是不想交的(互不影響)。當(dāng)求解一個(gè)問題規(guī)模很大很難直接求解,但是規(guī)模較小的時(shí)候問題很容易求解并且這個(gè)問題并且問題滿足分治算法的適用條件,那么就可以使用分治算法。

那么采用分治算法解決的問題需要 滿足那些條件(特征) 呢?

1 . 原問題規(guī)模通常比較大,不易直接解決,但問題縮小到一定程度就能較容易的解決。

2 . 問題可以分解為若干規(guī)模較小、求解方式相同(似)的子問題。且子問題之間求解是獨(dú)立的互不影響。

3 . 合并問題分解的子問題可以得到問題的解。

你可能會(huì)疑惑分治算法和遞歸有什么關(guān)系?其實(shí)分治重要的是一種思想,注重的是問題分、治、合并的過程。而遞歸是一種方式(工具),這種方式通過方法自己調(diào)用自己形成一個(gè)來回的過程,而分治可能就是利用了多次這樣的來回過程。

三、分治算法經(jīng)典問題

對于分治算法的經(jīng)典問題,重要的是其思想,因?yàn)槲覀兇蟛糠纸柚f歸去實(shí)現(xiàn),所以在代碼實(shí)現(xiàn)上大部分都是很簡單,而本篇也重在講述思想。

分治算法的經(jīng)典問題,個(gè)人將它分成兩大類:子問題完全獨(dú)立和子問題不完全獨(dú)立。

1 . 子問題完全獨(dú)立就是原問題的答案可完全由子問題的結(jié)果推出。

2 . 子問題不完全獨(dú)立,有些區(qū)間類的問題或者跨區(qū)間問題使用分治可能結(jié)果跨區(qū)間,在考慮問題的時(shí)候需要仔細(xì)借鑒下。

3.1、二分搜索

二分搜索是分治的一個(gè)實(shí)例,只不過二分搜索有著自己的特殊性

  • 序列有序
  • 結(jié)果為一個(gè)值

正常二分將一個(gè)完整的區(qū)間分成兩個(gè)區(qū)間,兩個(gè)區(qū)間本應(yīng)單獨(dú)找值然后確認(rèn)結(jié)果,但是通過有序的區(qū)間可以直接確定結(jié)果在那個(gè)區(qū)間,所以分的兩個(gè)區(qū)間只需要計(jì)算其中一個(gè)區(qū)間,然后繼續(xù)進(jìn)行一直到結(jié)束。實(shí)現(xiàn)方式有遞歸和非遞歸,但是非遞歸用的更多一些:

public int searchInsert(int[] nums, int target) {
  if(nums[0]>=target)return 0;//剪枝
  if(nums[nums.length-1]==target)return nums.length-1;//剪枝
  if(nums[nums.length-1]<target)return nums.length;
  int left=0,right=nums.length-1;
  while (left<right) {
    int mid=(left+right)/2;
    if(nums[mid]==target)
      return mid;
    else if (nums[mid]>target) {
      right=mid;
    }
    else {
      left=mid+1;
    }
  }
  return left;
}

3.2、快速排序

快排也是分治的一個(gè)實(shí)例,快排每一趟會(huì)選定一個(gè)數(shù),將比這個(gè)數(shù)小的放左面,比這個(gè)數(shù)大的放右面,然后遞歸分治求解兩個(gè)子區(qū)間,當(dāng)然快排因?yàn)樵诜值臅r(shí)候就做了很多工作,當(dāng)全部分到最底層的時(shí)候這個(gè)序列的值就是排序完的值。這是一種分而治之的體現(xiàn)。

public void quicksort(int [] a,int left,int right)
{
  int low=left;
  int high=right;
  //下面兩句的順序一定不能混,否則會(huì)產(chǎn)生數(shù)組越界?。。ery important?。?!
  if(low>high)//作為判斷是否截止條件
    return;
  int k=a[low];//額外空間k,取最左側(cè)的一個(gè)作為衡量,最后要求左側(cè)都比它小,右側(cè)都比它大。
  while(low<high)//這一輪要求把左側(cè)小于a[low],右側(cè)大于a[low]。
  {
    while(low<high&&a[high]>=k)//右側(cè)找到第一個(gè)小于k的停止
    {
      high--;
    }
    //這樣就找到第一個(gè)比它小的了
    a[low]=a[high];//放到low位置
    while(low<high&&a[low]<=k)//在low往右找到第一個(gè)大于k的,放到右側(cè)a[high]位置
    {
      low++;
    }
    a[high]=a[low];			
  }
  a[low]=k;//賦值然后左右遞歸分治求之
  quicksort(a, left, low-1);
  quicksort(a, low+1, right);		
}

3.3、歸并排序(逆序數(shù))

快排在分的時(shí)候做了很多工作,而歸并就是相反,歸并在分的時(shí)候按照數(shù)量均勻分,而合并時(shí)候已經(jīng)是兩兩有序的進(jìn)行合并的,因?yàn)閮蓚€(gè)有序序列O(n)級別的復(fù)雜度即可得到需要的結(jié)果。而逆序數(shù)在歸并排序基礎(chǔ)上變形同樣也是分治思想求解。

private static void mergesort(int[] array, int left, int right) {
  int mid=(left+right)/2;
  if(left<right)
  {
    mergesort(array, left, mid);
    mergesort(array, mid+1, right);
    merge(array, left,mid, right);
  }
}

private static void merge(int[] array, int l, int mid, int r) {
  int lindex=l;int rindex=mid+1;
  int team[]=new int[r-l+1];
  int teamindex=0;
  while (lindex<=mid&&rindex<=r) {//先左右比較合并
    if(array[lindex]<=array[rindex])
    {
      team[teamindex++]=array[lindex++];
    }
    else {				
      team[teamindex++]=array[rindex++];
    }
  }
  while(lindex<=mid)//當(dāng)一個(gè)越界后剩余按序列添加即可
  {
    team[teamindex++]=array[lindex++];

  }
  while(rindex<=r)
  {
    team[teamindex++]=array[rindex++];
  }	
  for(int i=0;i<teamindex;i++)
  {
    array[l+i]=team[i];
  }
}

3.4、最大子序列和

最大子序列和的問題我們可以使用動(dòng)態(tài)規(guī)劃的解法,但是也可以使用分治算法來解決問題,但是最大子序列和在合并的時(shí)候并不是簡單的合并,因?yàn)樽有蛄泻蜕婕暗揭粋€(gè)長度的問題,所以正確結(jié)果不一定全在最左側(cè)或者最右側(cè),而可能出現(xiàn)結(jié)果的區(qū)域?yàn)椋?/p>

  • 完全在中間的左側(cè)
  • 完全在中間的右側(cè)
  • 包含中間左右兩個(gè)節(jié)點(diǎn)的一個(gè)序列

用一張圖可以表示為:

所以在具體考慮的時(shí)候需要將無法遞歸得到結(jié)果的中間那個(gè)最大值串的結(jié)果也算出來參與左側(cè)、右側(cè)值得比較。

力扣53. 最大子序和在實(shí)現(xiàn)的代碼為:

public int maxSubArray(int[] nums) {
    int max=maxsub(nums,0,nums.length-1);
    return max;
}
int maxsub(int nums[],int left,int right)
{
    if(left==right)
        return  nums[left];
    int mid=(left+right)/2;
    int leftmax=maxsub(nums,left,mid);//左側(cè)最大
    int rightmax=maxsub(nums,mid+1,right);//右側(cè)最大

    int midleft=nums[mid];//中間往左
    int midright=nums[mid+1];//中間往右
    int team=0;
    for(int i=mid;i>=left;i--)
    {
        team+=nums[i];
        if(team>midleft)
            midleft=team;
    }
    team=0;
    for(int i=mid+1;i<=right;i++)
    {
        team+=nums[i];
        if(team>midright)
            midright=team;
    }
    int max=midleft+midright;//中間的最大值
    if(max<leftmax)
        max=leftmax;
    if(max<rightmax)
        max=rightmax;
    return  max;
}

3.5、最近點(diǎn)對

最近點(diǎn)對是一個(gè)分治非常成功的運(yùn)用之一。在二維坐標(biāo)軸上有若干個(gè)點(diǎn)坐標(biāo),讓你求出最近的兩個(gè)點(diǎn)的距離,如果讓你直接求那么枚舉暴力是個(gè)非常非常大的計(jì)算量,我們通常采用分治的方法來優(yōu)化這種問題。

如果直接分成兩部分分治計(jì)算你肯定會(huì)發(fā)現(xiàn)如果最短的如果一個(gè)在左一個(gè)在右會(huì)出現(xiàn)問題。我們可以優(yōu)化一下。

在具體的優(yōu)化方案上,按照x或者y的維度進(jìn)行考慮,將數(shù)據(jù)分成兩個(gè)區(qū)域,先分別計(jì)算(按照同方法)左右區(qū)域內(nèi)最短的點(diǎn)對。然后根據(jù)這個(gè)兩個(gè)中較短的距離向左和向右覆蓋,計(jì)算被覆蓋的左右點(diǎn)之間的距離,找到最小那個(gè)距離與當(dāng)前最短距離比較即可。

這樣你就可以發(fā)現(xiàn)就這個(gè)一次的操作(不考慮子情況),左側(cè)紅點(diǎn)就避免和右側(cè)大部分紅點(diǎn)進(jìn)行距離計(jì)算(O(n2)的時(shí)間復(fù)雜度)。事實(shí)上,在進(jìn)行左右區(qū)間內(nèi)部計(jì)算的時(shí)候,它其實(shí)也這樣遞歸的進(jìn)行很多次分治計(jì)算。如圖所示:

這樣下去就可以節(jié)省很多次的計(jì)算量。

但是這種分治會(huì)存在一種問題就是二維坐標(biāo)可能點(diǎn)都聚集某個(gè)方法某條軸那么可能效果并不明顯(點(diǎn)都在x=2附近對x分割作用就不大),需要注意一下。

ac的代碼為:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
public class Main {
    static int n;
    public static void main(String[] args) throws IOException {
        StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        //List<node>list=new ArrayList();
         while(in.nextToken()!=StreamTokenizer.TT_EOF)
         {
             n=(int)in.nval;if(n==0) {break;}
            node no[]=new node[n];
            
             for(int i=0;i<n;i++)
             {
                 in.nextToken();double x=in.nval;
                 in.nextToken();double y=in.nval;
                // list.add(new node(x,y));
                 no[i]=new node(x,y);
             }
             Arrays.sort(no, com);
            double min= search(no,0,n-1);
            out.println(String.format("%.2f", Math.sqrt(min)/2));out.flush();
         }         
    }
    private static double search(node[] no, int left,int right) {
        int mid=(right+left)/2;
        double minleng=0;
        if(left==right) {return Double.MAX_VALUE;}
        else if(left+1==right) {minleng= (no[left].x-no[right].x)*(no[left].x-no[right].x)+(no[left].y-no[right].y)*(no[left].y-no[right].y);}
        else minleng= min(search(no,left,mid),search(no,mid,right));
        int ll=mid;int rr=mid+1;
        while(no[mid].y-no[ll].y<=Math.sqrt(minleng)/2&&ll-1>=left) {ll--;}
        while(no[rr].y-no[mid].y<=Math.sqrt(minleng)/2&&rr+1<=right) {rr++;}
        for(int i=ll;i<rr;i++)
        {
            for(int j=i+1;j<rr+1;j++)
            {
                double team=0;
                if(Math.abs((no[i].x-no[j].x)*(no[i].x-no[j].x))>minleng) {continue;}
                else
                { 
                    team=(no[i].x-no[j].x)*(no[i].x-no[j].x)+(no[i].y-no[j].y)*(no[i].y-no[j].y);
                    if(team<minleng)minleng=team;
                }
            }
        }
        return minleng;
    
    }
    private static double min(double a, double b) {
        // TODO 自動(dòng)生成的方法存根
        return a<b?a:b;
    }
    static Comparator<node>com=new Comparator<node>() {

        @Override
        public int compare(node a1, node a2) {
            // TODO 自動(dòng)生成的方法存根
            return a1.y-a2.y>0?1:-1;
        }};
    static class node
    {
        double x;
        double y;
        public node(double x,double y)
        {
            this.x=x;
            this.y=y;
        }
    }
}

四、結(jié)語

到這里,分治算法就講這么多了,因?yàn)榉种嗡惴ㄖ匾谟诶斫馄渌枷耄€有一些典型的分治算法解決的問題,例如大整數(shù)乘法、Strassen矩陣乘法、棋盤覆蓋、線性時(shí)間選擇、循環(huán)賽日程表、漢諾塔等問題你可以自己研究其分治的思想和原理。

以上就是詳解Java實(shí)現(xiàn)分治算法的詳細(xì)內(nèi)容,更多關(guān)于詳解Java實(shí)現(xiàn)分治算法的資料請關(guān)注腳本之家其它相關(guān)文章!

相關(guān)文章

  • 深入探究Java線程不安全的原因與解決

    深入探究Java線程不安全的原因與解決

    線程不安全這個(gè)問題,一般在學(xué)Java時(shí),我們老師會(huì)讓我們背誦一段長長的話。"當(dāng)不同線程同時(shí)能訪問同一個(gè)變量時(shí),可能會(huì)導(dǎo)致線程不安全"。實(shí)際上,這句話重點(diǎn)想突出的只有原子性。而我們往往考慮線程不安全的原因,會(huì)從三方面進(jìn)行考慮:就是原子性,可見性,有序性
    2022-04-04
  • 如何用Netty實(shí)現(xiàn)高效的HTTP服務(wù)器

    如何用Netty實(shí)現(xiàn)高效的HTTP服務(wù)器

    這篇文章主要介紹了如何用Netty實(shí)現(xiàn)高效的HTTP服務(wù)器,對HTTP感興趣的同學(xué)可以參考一下
    2021-04-04
  • SpringBoot使用Minio進(jìn)行文件存儲的實(shí)現(xiàn)

    SpringBoot使用Minio進(jìn)行文件存儲的實(shí)現(xiàn)

    本文主要介紹了SpringBoot使用Minio進(jìn)行文件存儲的實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2022-07-07
  • Java設(shè)計(jì)模式之java訪問者模式詳解

    Java設(shè)計(jì)模式之java訪問者模式詳解

    這篇文章主要介紹了JAVA設(shè)計(jì)模式之訪問者模式,簡單說明了訪問者模式的原理,并結(jié)合實(shí)例分析了java訪問者模式的定義與用法,需要的朋友可以參考下
    2021-09-09
  • Spring Boot之搞定mongoTemplate的知識小結(jié)

    Spring Boot之搞定mongoTemplate的知識小結(jié)

    這篇文章主要介紹了Spring Boot之搞定mongoTemplate的知識小結(jié),本文給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2020-12-12
  • java設(shè)計(jì)模式:原始模型模式

    java設(shè)計(jì)模式:原始模型模式

    這篇文章主要為大家詳細(xì)介紹了Java設(shè)計(jì)模式之Prototype原型模式的相關(guān)資料,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2021-08-08
  • idea配置springboot熱部署終極解決辦法(解決熱部署失效問題)

    idea配置springboot熱部署終極解決辦法(解決熱部署失效問題)

    這篇文章主要介紹了idea配置springboot熱部署終極解決辦法(解決熱部署失效問題),本文通過實(shí)例代碼給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友參考下吧
    2020-07-07
  • Java AtomicInteger類使用方法實(shí)例講解

    Java AtomicInteger類使用方法實(shí)例講解

    這篇文章主要介紹了Java AtomicInteger類使用方法實(shí)例講解,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2020-06-06
  • 數(shù)組實(shí)現(xiàn)Java 自定義Queue隊(duì)列及應(yīng)用操作

    數(shù)組實(shí)現(xiàn)Java 自定義Queue隊(duì)列及應(yīng)用操作

    這篇文章主要介紹了數(shù)組實(shí)現(xiàn)Java 自定義Queue隊(duì)列及應(yīng)用操作,具有很好的參考價(jià)值,希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2021-06-06
  • Java中Swagger框架的使用詳解

    Java中Swagger框架的使用詳解

    這篇文章主要介紹了Java框架Swagger的使用詳解,在開發(fā)期間接口會(huì)因業(yè)務(wù)的變更頻繁而變動(dòng),如果需要實(shí)時(shí)更新接口文檔,這是一個(gè)費(fèi)時(shí)費(fèi)力的工作,Swagger應(yīng)運(yùn)而生,他可以輕松的整合進(jìn)框架并通過一系列注解生成強(qiáng)大的API文檔,需要的朋友可以參考下
    2023-08-08

最新評論