分治法-連結アルゴリズム設計
分治法-連結アルゴリズム設計
分治法とは何ですか.
分治戦略:円問題をn個の規模が小さく、構造が円問題に似ているサブ問題に分ける.これらの問題を鬼のように解決する.そして結果を統合すると,元の問題の解が得られる.
分治モードの各層の再帰には3つのステップがあります.
分解:元の問題を一連のサブ問題に分解する.
解決:各サブ問題を再帰的に解決する.サブ問題が小さい場合は、直接解きます.
≪マージ|Merge|emdw≫:サブ問題の解を元の問題の解にマージします.
一.問題の説明:
n個の数からなるシーケンスa 1,a 2,...,an;上記のシーケンスをマージソートアルゴリズムでソートします.
二.アルゴリズム分析
マージ・ソート・アルゴリズムは、上記のモードに完全に従っています.手順は次のとおりです.
分解:n個の要素をn/2個の要素を含む各サブシーケンスに分割する.
解決:マージソートアルゴリズムで2つのサブシーケンスを再帰的にソートします.
≪マージ|Merge|emdw≫:ソートされた2つのサブシーケンスをマージして、元のシーケンスのソート結果を取得します.
サブシーケンスをソートすると、長さが1の場合に再帰的に終了し、単一の要素はソートされたものとみなされます.
並べ替えアルゴリズムをマージする重要なステップは、並べ替えられた2つのサブシーケンスをマージすることです.マージのために、補助プロセスmerge(A,p,q,r)が導入され、Aは配列、p,q,rは配列の下にp<=qトランプを例にとると、既存の2つのトランプは、すでに順番に並んでいて、一番小さいのは一番上に置いています.今、私たちは2つのトランプを順番に並べたいと思っています.基本的な手順は、2つの山の中から小さい1枚を選択し、それを取り出し、ある山が完全に空になるまで出力山の中に下に置いて(または、ある山に哨兵札が現れるまで)、別の入力山の残りのカードをすべて出力山の上に置く.n回の比較が多いため,時間的複雑度はO(n)である.
集計ソートのアルゴリズム
三.効率分析
T(n)をn規模の問題の実行時間とする.問題の規模がn<=c(定数)のように十分小さい場合、その直接解は定数であり、O(1)とする.
問題をa個のサブ問題に分解すると仮定する.各サブ問題の規模は元の問題のn/bであり、この問題を分解し、結合する時間をD(n)とC(n)と仮定し、効率モデルはT(n)=aT(n/b)+D(n)+C(n)であり、master theoryによって知ることができ、時間複雑度T(n)=O(nlgn)である.
四.C実現
分治法とは何ですか.
分治戦略:円問題をn個の規模が小さく、構造が円問題に似ているサブ問題に分ける.これらの問題を鬼のように解決する.そして結果を統合すると,元の問題の解が得られる.
分治モードの各層の再帰には3つのステップがあります.
分解:元の問題を一連のサブ問題に分解する.
解決:各サブ問題を再帰的に解決する.サブ問題が小さい場合は、直接解きます.
≪マージ|Merge|emdw≫:サブ問題の解を元の問題の解にマージします.
一.問題の説明:
n個の数からなるシーケンスa 1,a 2,...,an;上記のシーケンスをマージソートアルゴリズムでソートします.
二.アルゴリズム分析
マージ・ソート・アルゴリズムは、上記のモードに完全に従っています.手順は次のとおりです.
分解:n個の要素をn/2個の要素を含む各サブシーケンスに分割する.
解決:マージソートアルゴリズムで2つのサブシーケンスを再帰的にソートします.
≪マージ|Merge|emdw≫:ソートされた2つのサブシーケンスをマージして、元のシーケンスのソート結果を取得します.
サブシーケンスをソートすると、長さが1の場合に再帰的に終了し、単一の要素はソートされたものとみなされます.
並べ替えアルゴリズムをマージする重要なステップは、並べ替えられた2つのサブシーケンスをマージすることです.マージのために、補助プロセスmerge(A,p,q,r)が導入され、Aは配列、p,q,rは配列の下にp<=q
Merge(A, p, q, r)
{
m1=q-p+1,m2=r-q;
L(1,m1),R(1, m2)；
/* L(1, m) ,R(1, m2)*/
for i = 1~m1
L(i) = A(p+i-1)
for j = 1~m1
R(j) = A(p+j)
L(m1+1)= ；R(m2+1) = ；
i=1; j=1;
for k = p~r
if L(i) <= R(j)
then A[k] = L(i);i=i+1;
else
then A[k] = R(j);j=j+1;
}集計ソートのアルゴリズム
Merge_sort(A, p, r)
{
if (p<r)
{
q={ (p+r)/2 }；
Merge_sort(A, p, q);
Merge_sort(A, q+1, r);
Merge (A, p, q, r);
}
}三.効率分析
T(n)をn規模の問題の実行時間とする.問題の規模がn<=c(定数)のように十分小さい場合、その直接解は定数であり、O(1)とする.
問題をa個のサブ問題に分解すると仮定する.各サブ問題の規模は元の問題のn/bであり、この問題を分解し、結合する時間をD(n)とC(n)と仮定し、効率モデルはT(n)=aT(n/b)+D(n)+C(n)であり、master theoryによって知ることができ、時間複雑度T(n)=O(nlgn)である.
四.C実現
/**
* merge - array[low,mid] array[mid+1,high]
* array[low,high],
* Param.：
* @array:
* @low：
* @mid：
* @high：
* Return：
*
*/
void merge(intarray[], int low, int high, int mid)
{
int i, j, k, tmp;
i = low;
j = mid + 1;
while (i < j && j <= high)
{
if (array[i] > array[j])
{
tmp = array[j];
for (k = j; k > i; k--)
array[k] = array[k - 1];
array[i] = tmp;
j++;
}
i++;
}
}
/**
* merge_sort - ,
* Param.：
* @array:
* @low：
* @high：
* Return：
*
*/
void merge_sort(intarray[], int low, int high)
{
int mid;
if (low >= high)
return;
mid = (low + high) / 2;
merge_sort(array, low, mid);
merge_sort(array, mid + 1, high);
merge(array, low, high, mid);
}