[計算機アルゴリズム]Ch 3分割征服アルゴリズム(2)

사진을 클릭하면 PDF 정리본 다운로드 링크로 이어집니다.

🧐 マスターファイルの整理

点火式がT(n)=aT(n/b)+ndT(n)=aT(n/b)+n^dT(n)=aT(n/b)+ndである場合、aaa、bbb、dddの大きさに応じて、T(n)T(n)T(n)
(ただし、T(1)=O(1)T(1)=O(1)T(1)=O(1)=O(1)=O(1)であり、O(nd)O(n^d)O(nd)ではなくndn^dnd(n^d)O(nd)でも同様に計算される.)

🧐 3.3問題の選択（数値問題の検索）

選択問題vs選択ソート

선택문제 = 이진탐색 + 퀵 정렬
선택정렬 = 최솟값을 왼쪽에 고정해나감

nnn個の数字のkkkの2番目の小さな数字(入力された数字がそれぞれ異なると仮定)
1)1)最小数kk回を見つける.ただし、最小数値が見つかったら、入力からその数値を削除してください.
2)2)2)昇順に数字を並べてkkの2番目の数字を探す.
しかしながら、上記のアルゴリズムは、それぞれ最悪の場合のO(kn)O(kn)O(kn)とO(nlogn)O(nlogn)O(nlogn)の時間的複雑さを有する.効果的な解決策はありませんか?

バイナリナビゲーション思想に基づく方法を適用し,高速ソートで示すようにpivotpivotを選択し分割する.

この場合,アルゴリズムは問題を2つの局所問題に分割し,そのうちの1つの局所問題を考慮する必要はない.

局所問題の大きさを不定の大きさに減らす形式の分割征服アルゴリズム.

👩🏻‍💻 Cコードで表現すると?

int partition(int list[], int left, int right)
{
    int pivot, temp, low, high;
    
    pivot = list[left];
    low = left;
    high = right + 1;
  
    do
    {
        do
            low++;
        while(list[low] < pivot); 
        
        do
            high--;
        while(list[high] > pivot);
        
        if(low < high)
            SWAP(list[low], list[high], temp);
            
    } while(low < high);
    
    SWAP(list[left], list[high], temp);
    
    return high;
}

int findKth(int list[], int left, int right, int k)
{
    int p = partition(list, left, right);
    int s = (p - 1) - left + 1;
    
    if(k <= s)
        return findKth(list, left, p - 1, k);
    else if(k == s + 1)
        return list[p];
    else
        return findKth(list, p + 1, right, k - s - 1);
}

選択アルゴリズムは分割征服アルゴリズムであり,ランダムアルゴリズムでもある.
これは、

選択アルゴリズムの1行目において、回転軸ピボットがランダムに決定されたためである.

のpivotpivotが入力を片側に分割しすぎると、アルゴリズムの実行時間が長くなります.

偏分の確率はコインを投げたときに片面が現れる確率と同じです.

good/bad分割の定義

分割後の2つのグループの1つのサイズが入力サイズの3/43/43/4に等しい場合、または分割が大きい場合、bad分割として定義される.△良い分割は正反対だ.

の場合、分割された回転軸が選択される確率と、分割された回転軸が選択される確率はそれぞれ1/21/21である.

ピボットをランダムに決定すると、良好な分割の確率は1/21/21である.

は平均222回連続して回転ピボットをランダムに決定し,良好な分割が可能である.

good分割を連続的に完了した場合のみの時間的複雑度を求め,その値に222を乗じ,平均的に時間的複雑度を得た.

入力寸法はnnnから3/43/43/4倍連続的に減少し、寸法が111の場合、再分割できない.
⇒ n+3/4n+…+(3/4)inn + 3/4n + … + (3/4)^inn+3/4n+…+(3/4)in
=n[1+3/4+…+(3/4)i]= n[1 + 3/4 + … + (3/4)^i]=n[1+3/4+…+(3/4)i]
≤2n=O(n)≤ 2n = O(n)≤2n=O(n)
⇒ 2×O(n)=O(n)2 × O(n) = O(n)2×O(n)=O(n)

アルゴリズムとバイナリナビゲーションの選択

そうじせい

バイナリナビゲーション分割時に1/21/21の範囲を絞る、検索したいデジタルナビゲーション

.

選択アルゴリズムはpivot pivot pivotに分割され、範囲を縮小し、デジタルナビゲーションで

を検索する.

共通点

の一部の問題は、統合する必要はありません.

ApplicationsApplicationsApplications

アルゴリズムは、データ分析の中央値を検索するために選択される.

🧐 3.4最近接触したペアの検索

与えられた

2次元平面上のnnn個の点を入力すると、最近の一対の点の問題が検索される.

👨🏻‍🔬 無差別置換アルゴリズム(brute force)

各点について2点間の距離を計算し、最も近い点のペアを探します.
⇒ n(n−1)/2=O(n2)n(n-1)/2 = O(n^2)n(n−1)/2=O(n2)
一対の距離の計算はO(1)O(1)O(1)O(1)
時間複雑度:O(n 2)×O(1)=O(n2)O(n2) × O(1) = O(n^2)O(n2)×O(1)=O(n2)

👩🏻‍💻 Cコードで表現すると?

void closetPairIter (Point p[])
{
	double dMin = 10000000.0, d;
    int iMin, jMin;

    for (int i = 0; i < N - 1; i++)
    {
    for (int j = i + 1; j < N; j++)
	{
		d = dist (p[i], p[j]);
		if (d < dMin)
		{
			dMin = d;
			iMin = i;
			jMin = j;
		}
	}
}

  printf ("[%d %d] [%d %d] %.2f\n", p[iMin].x, p[iMin].y, p[jMin].x, p[jMin].y, dMin);
}

👨🏻‍🔬 分割征服アルゴリズム

nnn個の点を1/21/21/2に分割し,各局所問題において最近接触点対を探索し,222個の局所解において短距離離点対を探索した.
中間領域内のポイントに近いポイントペアがあることを確認します.
時間複雑度:O(nlogn)×logn=O(nlog2n)O(nlogn) × logn = O(nlog^2n)O(nlogn)×logn=O(nlog2n)
yyy座標で入力点をプリアライメントすると、入力点をO(nlogn)O(nlogn)O(nlogn)O(nlogn)に上げることができます.

👩🏻‍💻 意図コード表現なら?

Alg ClosestPair(S)
input array S sorted by value of x
output distance of closest pair
1. if(i <= 3) return closest distance
2. divide S -> S_L, S_R
3. CP_L = ClosestPair(S_L)
4. CP_R = ClosestPair(S_R)
5. d = min{dist(CP_L), dist(CP_R)}, get CP_C
6. return min{CP_L, CP_C, CP_R}

👩🏻‍💻 Cコードで表現すると?

double DMZCheck(Point p[], int left, int right, double d)
{
    insertionSortY(p);
    for(int i = left; i <= right; ++i)
    {
        for(int j = i+1; j <= right; j++)
        {
            if(p[j].y - p[i].y > d)
                break;
            double tmp = dist(p[i], p[j]);
            d = d < tmp ? d : tmp;
        }
    }
    return d;
}

double closestPairRecur(Point p[], int left, int right)
{
    int size = right - left + 1;
    double min;
    
    if(size == 2)
        return dist(p[left], p[right]);
        
    else if(size == 3){
        double a = dist(p[left], p[left + 1]);
        double b = dist(p[left + 1], p[left + 2]);
        double c = dist(p[left + 2], p[left + 3]);
        return min(a, b, c);
    }
    else
    {
        int mid = (left + right) / 2;
        double a =
                 closestPairRecur(p, left, mid);
        double b =
           closestPairRecur(p, mid + 1, right);
        min(a, b);
        return DMZCheck(p, left, right, min);
    }
}

🧐 3.5. 分割征服応用上の注意事項

分割征服が不当である.

分割入力のたびに,分割部分問題の入力サイズの和が分割前の入力サイズより大きい.

피보나치 문제 (분할대신 반복으로 풀 것)

ふくごうじゅうごうプロセス

幾何学に関連する多くの問題は,幾何学的問題の特性がそのフィッティング過程が問題の解決に良く適合することを決定するため,効率的な分割征服アルゴリズムで解決される.

💡 サマリ

分割とマージ
与えられた問題の入力を分割することによって問題を解決(征服)するアルゴリズム.
連結ソート
n個の入力をn/2 n/2 n/2個で222個の局所問題に分割し,各局所問題を循環連結並べ替え,次いで並べ替え(征服)のアルゴリズムを連結する.時間的複雑度はO(nlogn)O(nlogn)O(nlogn),空間的複雑度はO(n)O(n)O(n)であった.
クイックソート
pivotpivotを基準に、小さな数字を左に、大きな数字を右に分けます.分割された部分の問題に対して,同じプロセスをループしてソートするアルゴリズム.時間的複雑度が最も良いのはO(nlogn)O(nlogn)O(nlogn)であり,平均的にO(nlogn)O(nlogn)O(nlogn)であり,最悪の場合はO(n 2 o)O(n^2)O(n 2)である.
質問の選択
kkの2番目の小数点の問題を探して、入力の中で急速にソートするようにpivotpivotを選択して分割して、それからkkの2番目の小数点を含む部分を循環してブラウズします.時間複雑度は平均でO(n)O(n)O(n)O(n)であった.
最近の接触は問題に対して
nnn個の点を1/21/21/2に分割し,各局所問題の最近の接触点の対中小値を求めた.この値が中間領域内の点より小さいかどうかを確認して、最も近いコンタクトペアを検索します.分割征服方式を採用すると,昇格時間の複雑さはO(nlogn)O(nlogn)O(nlogn)である.
分割征服の適用に関する注意事項
分割前と比較して,分割後入力サイズの和が大きいほど,分割征服は不適切である.また、採用(征服)過程が簡単かどうかも観察しなければならない.