天天看點
傳回

001--算法之"高手過招"[分治算法專題]

算法之"高手過招"

1.1 什麼是分治政策算法?

在計算機科學中,分治政策是非常重要的算法思想. 字面上的意思就是把一個複雜問題分解成2個或者多個相同或者相似的子問題. 再子問題的分解成更小的子問題; 直到最後的子問題可以簡單的直接求解. 再将子問題的結果合并得到原問題的結果;

這樣的方式,比如常用的排序算法中, 快速排序以及歸并排序都是利用了分治政策算法的思想實作的. 在分治政策中, 我們遞歸地求解一個問題, 在每層遞歸中應用如下三個步驟:

  • 分解(Divide)步驟, 将問題劃分為一些子問題. 子問題的形式與原問題一樣. 隻是規模更小;
  • 解決(Conquer)步驟,遞歸地求解出子問題,如果子問題的規模足夠小,即停止遞歸.直接求解;
  • 合并(Combine)步驟,将子問題的解組合成原問題的解;

當子問題足夠大, 需要遞歸求解時. 我們就稱之為"遞歸情況". 當子問題變的足夠小, 不再需要遞歸時, 這時遞歸就已經"觸底". 進入了基本情況;

并不是所有的問題都能化解成完全一樣的子問題. 也會出現需要求解與原問題不完全一樣的子問題. 接下來在這一階段的課程,我們會看到更多基于分治政策的算法.

分治政策,在了解以及設計分治政策的算法的能力需要一定時間去掌握.它需要運用歸納法去證明一個理論. 為了使得遞歸能夠被推行. 很多時候需要用一個較為概括或複雜的問題去取代原有問題,而且并沒有一個系統性的方法去适當的概括問題;

分治算法需要不錯的數學歸納能力.因為分治政策的算法通常需要以數學歸納法來驗證, 它的計算成本則多數以求解的遞歸關系式來判定;

由于分治政策的特性, 它最直接的表現形式常常以遞歸出現.

1.2 連續數列

  • 難度系數: ☆☆☆
  • 題目來源: LeetCode 下分治政策專題
  • 題目描述: 給定一個整數數組,找出總和最大的連續數列, 并傳回總和;
  • 輸入: [-2,1,-3,4,-1,2,1,-5,4]
  • 輸出: 6
  • 解釋: 連續子數組[4,-1,2,-1];
  • 題目解讀:
  • 實際上, 這個題目就是單純的擷取從一個數組中,找出連續索引值下元素相加的總和最大的序列; 例如題目描述的例子. 從頭到尾進行查找, 使得連續的元素相機得到一個最大的總和;
  • 關鍵詞: 連續數列, 最大, 整數數組. 總和;
  • 出現過企業面試題: 百度

1.2.1 暴力法

LeetCode 執行結果

暴力算法思路

  • 判斷數組中的元素個數, 如果元素個數為0,則直接傳回0;
  • 判斷數組中的元素個數, 如果元素個數為1,則直接傳回索引為0下的元素值;
  • 定義臨時變量: i,temp,maxValue; 預設将maxValue 設定一個極小的值作為初始化值;
  • 開始循環,
  • 循環起始值i = 0;
  • 循環結束條件: 當i從頭到尾都周遊了一次;
  • 循環遞增條件: i每次自增1;
  • 在循環體中;
  • 将臨時變量temp 記錄從0~i的和的累積;
  • 判斷目前的temp 是否大于 maxVaue. 如果大于MaxValue 則更新maxValue;
  • 判斷目前的temp如果小于0的情況出現,則将temp 指派為0;
  • 最後傳回maxValue;

暴力算法代碼實作 

int maxSubArray(int* nums, int numsSize){
    if(numsSize==0) return 0;
    if(numsSize==1) return nums[0];
    int i=0,temp=0,maxValue=-1024;
    for(i=0;i<numsSize;i++)
    {
        temp=temp+nums[i];
        if(temp>maxValue) maxValue=temp;
        if(temp<0) temp=0;
    }
    return maxValue;
}

複制

執行過程動畫效果

溫馨提示: 上圖為動圖效果. 網頁閱讀更佳

1.2.2 分治政策

站在分治政策的角度下思考, 求最大連續數組. 我們可以預估到最大連續數組的和 有可能出現的3個位置如下:

  1. 數組的左半部分的最大連續數組和;
  2. 數組的右半部分的最大連續數組和;
  3. 橫跨數組的左半部分和右半部分得到最大連續數組和;
  4. 三者比較大小, 最大者即為我們所求的最大連續數組的和.

LeetCode 執行結果

接下來,我們分析案例中提供的數組. 來推演 分治政策的算法思想;

如果推演過程,數組中元素太多.可能會造成大家對于 分治政策中提出的 關于有可能出現最大連續數組和的3個猜想造成了解負擔;

是以我們假設此時 數組中隻有2個元素. 數組nums[2] = {-2,1}; 其中-2和1隻是随機設計的數字.

也就是 這2個數字最多組成3個可能性;

  • -2; 表示數組左半部分的有可能是最大連續數組的和;
  • -2 + 1 ; 表示數組橫跨左半部分和右半邊部分有可能是連續數組的和;
  • 1 ; 表示數組右半部分有可能是最大連續數組的和;
  • 最後, 比較這3個數字,取最大就能獲得最大連續數組的和;

分治政策算法思路

分析: 分治政策在開篇,我們就談過. 分治政策的本質就是将問題拆解成最小子問題, 再将子問題的結合進行合并; 而連續數列問題, 其實就可以用到分治政策中的遞歸的方式來進行解決; 剛剛我們通過對2個元素的數列進行小基數資料的推演. 我們需要将數列拆解左右2個半部分, 依次遞歸拆解. 直到隻剩下一個數字時就觸碰到遞歸的底線; 那麼現在我們捋順一下這個問題的思路;

思路:

  • 将數列一分為二. 求解mid = left + (right - left)/2 ; 那麼為什麼要這麼計算mid 是因為數列在不斷拆解的過程,數列本身就被折斷了. 但是我們不能記錄錯誤的mid; mid 還是基于nums 原始數組的index ;
  • 遞歸求解數列左半部分的和 則調用 subMaxValue(nums, left, mid);
  • 求出左半部分和之後, 則繼續求解從left 跨越mid 到 right 這橫跨中間部分的和; MidValue(nums,left,mid,right);
  • 繼續遞歸求解數列右半部分的和.則調用 subMaxValue(nums, mid+1,right);
  • 最後在每一次遞歸回調上層之前,判斷 left_sum,mid_sum,right_sum**** 誰的值更大,則傳回上一層遞歸
  • 繼續遞歸復原. 直到所有的遞歸都復原到入口時,就求解出來 連續數列的最大和

分治政策代碼實作 

//
//  main.c
//  001--連續數組(分治政策)
//
//  Created by CC老師 on 2020/9/7.
//  Copyright © 2020 CC老師. All rights reserved.
//

#include <stdio.h>
//宏定義無窮小
#define INF -2147483647
//求a和b的最大值
#define max( a , b ) ( a > b ? a : b )

//求跨越中點mid的最小子數組和
int MidValue( int * nums , int left , int mid , int right ){

    int left_sum = INF , right_sum = INF;
    int sum = 0;

    //求中點最半部分和
    for( int i = mid ; i >= left ; i-- ){

        sum += *( nums + i );

        if( sum > left_sum ){

            left_sum = sum;

        }

    }

    sum = 0;

    //求中點右半部分和
    for( mid++ ; mid <= right ; mid++ ){

        sum += *( nums + mid );

        if( sum > right_sum ){

            right_sum = sum;

        }

    }

    return right_sum + left_sum;

}

int subMaxValue( int * nums , int left , int right ){

    if( left >= right ){

        return *( nums + left );

    }

    int mid = left + ( right - left ) / 2;
    //僅求中點左部分和
    int left_sum = subMaxValue( nums , left , mid );
    //求跨越中點的和
    int mid_sum = MidValue( nums , left , mid , right );
    //求中點右部分和
    int right_sum = subMaxValue( nums , mid + 1 , right );
    
    return max( left_sum , max( right_sum , mid_sum ) );

}

int maxSubArray( int * nums , int numsSize ){

    return subMaxValue( nums , 0 , numsSize - 1 );

}

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n");
    //int nums[] = {-2,1,-3};
    int nums[] = {-2,1,-3,4,-1,2,1,-5,4};
    int maxSum = maxSubArray(nums, 9);
    printf("%d\n",maxSum);
    return 0;
}

複制

總結與分析

連續數列這個問題, 我們實作了2種方法. 第一種是暴力法, 第二種是分治政策; 但是從代碼實作的結果以及他們的執行時間和記憶體空間占用上,可以發現第一種方法更有優勢. 是以在解決算法問題時, 并不是單純的認為分治政策的解決的方案就會比暴力法進階. 其實算法重要的還是比較他們的時間/空間複雜度. 更重要的是從不同的解決政策去實作算法, 最大的收益是開拓的解決問題的思維方式;

實際該問題,還有一種解決方案. 是動态規劃. 因為該篇章的主角是 "分治政策" 是以我們就不在這篇中 來進行喧賓奪主的事情. 後續會有專門關于 動态規劃的篇章,我們在繼續延伸學習.

作為一個開發者，有一個學習的氛圍跟一個交流圈子特别重要，這是一個我的iOS交流群：642363427不管你是小白還是大牛歡迎入駐 ，分享BAT,阿裡面試題、面試經驗，讨論技術， 大家一起交流學習成長！

算法之"高手過招" 專欄會以 幾大算法政策為主題的進行不斷更新. 後續會繼續更新"分治政策"篇章.

緻謝!

該文章,僅獻給在程式設計路上, 持續熱愛算法的開發者

文章如有錯誤,歡迎指正

作者：CC老師_HelloCoder

連結：https://www.jianshu.com/p/eec69aaade8d

上一篇: Jmeter分布式壓測部署說明
下一篇: 解決component ‘*.OCX’控件出錯