算法詳解之分治法具體實(shí)現(xiàn)
分治算法的基本思想是將一個(gè)規(guī)模為N的問(wèn)題分解為K個(gè)規(guī)模較小的子問(wèn)題,這些子問(wèn)題相互獨(dú)立且與原問(wèn)題性質(zhì)相同。求出子問(wèn)題的解,就可得到原問(wèn)題的解。
分治法解題的一般步驟:
(1)分解,將要解決的問(wèn)題劃分成若干規(guī)模較小的同類問(wèn)題;
(2)求解,當(dāng)子問(wèn)題劃分得足夠小時(shí),用較簡(jiǎn)單的方法解決;
(3)合并,按原問(wèn)題的要求,將子問(wèn)題的解逐層合并構(gòu)成原問(wèn)題的解。
一言以蔽之:分治法的設(shè)計(jì)思想是,將一個(gè)難以直接解決的大問(wèn)題,分割成一些規(guī)模較小的相同問(wèn)題,以便各個(gè)擊破,分而治之。
在認(rèn)識(shí)分治之前很有必要先了解一下遞歸,當(dāng)然,遞歸也是最基本的編程問(wèn)題,一般接觸過(guò)編程的人都會(huì)對(duì)遞歸有一些認(rèn)識(shí).為什么要先了解遞歸呢?你看,根據(jù)上面所說(shuō)的,我們就要將一個(gè)問(wèn)題分成若干個(gè)小問(wèn)題,然后一一求解并且最后合并,這就是一個(gè)遞歸的問(wèn)題,遞歸的去分解自身,遞歸的去解決每一個(gè)小問(wèn)題,然后合并…
關(guān)于遞歸,這里舉一個(gè)最簡(jiǎn)單的例子,求N??;
我們只需要定義函數(shù)
int calculate(int n)
{
if(n==1)
return 1;
else
return n*calculate(n-1); //調(diào)用自身…
}
好了,有了遞歸的鋪墊,我們下來(lái)來(lái)看一看一個(gè)分治算法的問(wèn)題,歸并排序問(wèn)題…
基本思想:
將待排序元素分成大小大致相同的2個(gè)子集合(遞歸直到最小的排序單元),分別對(duì)2個(gè)子集合進(jìn)行排序,最終將排好序的子集合合并成為所要求的排好序的集合。
下面我們用一張圖來(lái)展示整個(gè)流程,最下面的(姑且叫他第一層)是原始數(shù)組分成了8個(gè)最小排序問(wèn)題,各自只有一個(gè)元素,故不需要排序,大家可以看到,我們通過(guò)分而治之的思想把對(duì)最初數(shù)組的排序分為了若干個(gè)只有一個(gè)元素的小數(shù)組的排序,然后第二層,我們進(jìn)行了合并,將每?jī)蓚€(gè)最小排序結(jié)果合并為有兩個(gè)元素的數(shù)組,然后逐層往上進(jìn)行合并,就有了最后的結(jié)果…
下面我們來(lái)看一下這個(gè)算法的具體實(shí)現(xiàn),下面的MERGE-SORT (A, p, r)表示對(duì)數(shù)組A[p->r]的排序過(guò)程.其中p->r代表從p到r.
MERGE-SORT (A, p, r)
1. IF p < r // 進(jìn)行A[p->r]的排序過(guò)程自然需要p<r的前提條件
2. THEN q = [(p + r)/2] // 將當(dāng)前的排序問(wèn)題一分為二,分別進(jìn)行處理
3. MERGE-SORT (A, p, q) //繼續(xù)遞歸看能不能將問(wèn)題繼續(xù)一分為二,處理A[p->q]的排序
4. MERGE-SORT (A, q + 1, r) // 繼續(xù)遞歸看能不能將問(wèn)題繼續(xù)一分為二處理A[q+1->r]的排序
5. MERGE (A, p, q, r) // 合并當(dāng)前結(jié)果
到這里,分治算法的精髓已經(jīng)出來(lái)了,我們通過(guò)遞歸將問(wèn)題進(jìn)行分解到足夠小…繼而進(jìn)行結(jié)果計(jì)算…然后再將結(jié)果合并.
下面來(lái)處理一下邊角料的工作,呵呵,讓大家看到一個(gè)完整的歸并排序的例子,整個(gè)算法總結(jié)系列我都沒有很好的使用偽代碼,而是使用我認(rèn)為廣泛使用的C語(yǔ)言代碼來(lái)進(jìn)行代碼詮釋.實(shí)際上,描述算法最好還是使用偽代碼比較好,這里我對(duì)我前面的四篇文章沒有使用偽代碼而小小的鄙視一下自己,太不專業(yè)了..呵呵
以下算法MERGE (A, p, q, r )表示合并A[p->q]和A[q+1->r]這兩個(gè)已經(jīng)排序好的數(shù)組
MERGE (A, p, q, r )
1. n1 ← q − p + 1 //計(jì)算A[p->q]的長(zhǎng)度
2. n2 ← r − q //計(jì)算A[q+1->r]的長(zhǎng)度
3. Create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1] //創(chuàng)建兩個(gè)數(shù)組
4. FOR i ← 1 TO n1
5. DO L[i] ← A[p + i − 1]
6. FOR j ← 1 TO n2
7. DO R[j] ← A[q + j ] //4-7行是將原數(shù)組中A[p->r]的元素取出到新創(chuàng)建的數(shù)組,我們的操作是基于臨時(shí)數(shù)組的操作
8. L[n1 + 1] ← ∞
9. R[n2 + 1] ← ∞ //8-9行設(shè)置界限..
10. i ← 1
11. j ← 1
12. FOR k ← p TO r
13. DO IF L[i ] ≤ R[ j]
14. THEN A[k] ← L[i]
15. i ← i + 1
16. ELSE A[k] ← R[j]
17. j ← j + 1 //12-17行進(jìn)行排序合
這里我還是提供一個(gè)具體的實(shí)現(xiàn),請(qǐng)見下面的代碼
C語(yǔ)言代碼
關(guān)于代碼注釋,請(qǐng)見博客上面的偽代碼注釋..
#include<stdio.h>
int L[100],R[100];
void merge(int numbers[],int left, int mid, int right)
{
int n1=mid-left+1;
int n2=right-mid;
int i,j,k;
for(i=1;i<=n1;i++)
L[i]=numbers[left+i-1];
for( j=1;j<=n2;j++)
R[j]=numbers[mid+j];
L[n1+1]=99999;
R[n2+1]=99999;
i=1;
j=1;
for(k=left;k<=right;k++)
if(L[i]<=R[j])
{
numbers[k]=L[i];
i++;
}
else
{
numbers[k]=R[j];
j++;
}
}
void mergeSort(int numbers[],int left, int right)
{
if(left<right)
{
int mid;
mid = (right + left) / 2;
mergeSort(numbers, left, mid);
mergeSort(numbers, mid+1, right);
merge(numbers,left, mid, right);
}
}
int main()
{
int numbers[]={5,2,4,6,1,3,2,6};
mergeSort(numbers,0,7);
for(int i=0;i<8;i++)
printf("%d",numbers[i]);
}
歸并排序算法的時(shí)間復(fù)雜度是O(nlogn),對(duì)于冒泡排序的O(n*n),效率還有有比較好的提高..
其實(shí)本人原來(lái)在學(xué)習(xí)的時(shí)候好長(zhǎng)一段時(shí)間不理解為什么時(shí)間復(fù)雜度會(huì)是O(nlogn),像冒泡排序就比較好理解,有兩個(gè)for循環(huán),問(wèn)題的規(guī)模隨著n變大而變大,算法時(shí)間復(fù)雜度自然就是O(n*n),后面花了一些時(shí)間來(lái)閱讀一些資料才明白其原理,這里我已經(jīng)將資料地址放到了本文最后,有興趣的也可以去看看.簡(jiǎn)單的描述一下為什么會(huì)是O(nlogn)
大家看看,我們的例子,解一個(gè)8個(gè)元素的數(shù)組,我們用到了幾層?是四層,假設(shè)我們這里有n個(gè)元素,我們會(huì)用到多少層?根據(jù)一定的歸納總結(jié),我們知道我們會(huì)用到(lgn)+1層..(lgn)+1層需要用到lgn層次的合并算法.現(xiàn)在再看看MERGE (A, p, q, r )的復(fù)雜度是多少,毫無(wú)疑問(wèn)O(n),故其歸并排序的算法時(shí)間復(fù)雜度是O(nlogn).當(dāng)然這個(gè)結(jié)果還可以通過(guò)其他的方法計(jì)算出來(lái),我這里是口語(yǔ)話最簡(jiǎn)潔的一種..
下面來(lái)一張算法時(shí)間復(fù)雜度的與n規(guī)模的關(guān)系圖..
相關(guān)文章
C++小利器之std::bind參數(shù)綁定包裝器的使用詳解
從 C++11 開始,標(biāo)準(zhǔn)庫(kù)提供了 std::bind 用于綁定函數(shù) f 和調(diào)用參數(shù),返回一個(gè)新可調(diào)用函數(shù)對(duì)象 fn,下面就跟隨小編一起深入了解一下std::bind的具體使用吧2023-12-12Qt圖形圖像開發(fā)之曲線圖表模塊QChart庫(kù)讀取/設(shè)置X軸的顯示區(qū)間
這篇文章主要介紹了Qt圖形圖像開發(fā)之曲線圖表模塊QChart庫(kù)讀取/設(shè)置X軸的顯示區(qū)間,需要的朋友可以參考下2020-03-03C語(yǔ)言實(shí)現(xiàn)BMP格式圖片轉(zhuǎn)化為灰度
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)BMP格式圖片轉(zhuǎn)化為灰度,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-10-10opencv2實(shí)現(xiàn)10張圖像上下左右拼接融合
這篇文章主要為大家詳細(xì)介紹了opencv2實(shí)現(xiàn)10張圖像上下左右拼接融合,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2020-03-03Qt實(shí)現(xiàn)繪制一個(gè)簡(jiǎn)單多邊形的示例代碼
QT提供了圖形繪制接口QPainter,通過(guò)該接口可以繪制多種圖形,包括多邊形。本文就來(lái)利用它實(shí)現(xiàn)繪制一個(gè)簡(jiǎn)單的多邊形,感興趣的可以嘗試一下2022-11-11C語(yǔ)言實(shí)現(xiàn)flappy bird游戲
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)flappy bird小游戲,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2018-12-12C++ 遞歸遍歷文件并計(jì)算MD5的實(shí)例代碼
在本篇文章里小編給大家整理的是一篇關(guān)于C++ 遞歸遍歷文件并計(jì)算MD5的實(shí)例代碼,有興趣的朋友們可以學(xué)習(xí)參考下。2021-07-07C語(yǔ)言實(shí)現(xiàn)的學(xué)生選課系統(tǒng)代碼分享
這篇文章主要介紹了C語(yǔ)言實(shí)現(xiàn)的學(xué)生選課系統(tǒng)代碼分享,具有一定參考價(jià)值,需要的朋友可以了解下。2017-10-10Qt數(shù)據(jù)庫(kù)應(yīng)用之實(shí)現(xiàn)文件編碼格式識(shí)別
在做數(shù)據(jù)導(dǎo)入導(dǎo)出的過(guò)程中,如果應(yīng)用場(chǎng)景多了,相信各位都會(huì)遇到一個(gè)問(wèn)題就是文件編碼的問(wèn)題。本文將用Qt實(shí)現(xiàn)文件編碼格式識(shí)別,感興趣的可以了解一下2022-06-06