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

算法詳解之分治法具體實(shí)現(xiàn)

 更新時(shí)間:2014年02月17日 15:29:16   作者:  
這篇文章主要介紹了算法詳解之分治法具體實(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ù)

復(fù)制代碼 代碼如下:

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)見博客上面的偽代碼注釋..

復(fù)制代碼 代碼如下:

#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)文章

最新評(píng)論