最も大きなサブアレイ問題のアルゴリズム比較

title:最大サブアレイ問題アルゴリズム比較date:2019-02-08 17:23:34 tags:Algorithms
『計算ガイド』4.1-3.暴力法と分治法を比較する.
まず構造体を定義します.

typedef struct {
	int left;
	int right;
	int max;
}ans;

テスト用のランダム配列を生成します.

#include 
#define random(x) (rand()%x)

srand((int)time(0));
int A[NUM];
for (int i = 0; i < NUM; i++) {
	A[i] = random(100) - 50;	
}

暴力の求め方
コード

ans MaxSubarray_violent(int A[], int low, int high) {
	ans a {low, high, A[low]};
	if (low == high) return a;//  low<=high
	for (int i = low; i <= high; i++) {
		int sum = 0;
		for (int j = i; j <= high; j++) {
			sum += A[j];
			if (sum > a.max) {
				a.max = sum;
				a.left = i;
				a.right = j;
			}
		}
	}
	return a;
}

分析
運転時間f(n)=c 1 n²+c 2 n+c 3時間複雑度O(n²)
分割統治
考え方
まず、問題を3つの状況に分けます.一番大きなサブアレイは左半分、右半分、中間点を超えています.前の二つは再帰と呼ばれ、再帰し続ける必要があります.最後の一つは基本状況と言います.直接解決できます.中点を越える場合は中点から左、右に一番大きなサブアレイを探して統合すればいいです.
コード

ans MaxSubarray_divide(int A[], int low, int high) {
	ans a = { low,high,A[low] };
	if (low == high) return a;
	ans left, right, cross;
	int mid = (low + high) / 2;
	left = MaxSubarray_divide(A, low, mid);
	right = MaxSubarray_divide(A, mid + 1, high);
	cross = MaxSubarray_divide_crossing(A, low, mid, high);
	if (left.max > right.max&&left.max > cross.max) return left;
	else if (right.max > left.max&&right.max > cross.max) return right;
	else return cross;
}

ans MaxSubarray_divide_crossing(int A[], int low, int mid, int high) {
	int sum = 0, left_max = INT_MIN, right_max = INT_MIN;
	ans a;
	for (int i = mid; i >= low; i--) {
		sum += A[i];
		if (sum > left_max) {
			left_max = sum;
			a.left = i;
		}
	}
	sum = 0;
	for (int i = mid + 1; i <= high; i++) {
		sum += A[i];
		if (sum > right_max) {
			right_max = sum;
			a.right = i;
		}
	}
	a.max = left_max + right_max;
	return a;
}

分析
分治時間の複雑さはnlgnである.
交差点
テーマは、この2つのアルゴリズムの性能交差点を求めることを要求します.数学的な角度で考えると、すなわち解方程式です.c 1 n＋c 2 n＋c 3=nlgn.関数画像からは、nが小さいので、左に右にあります.
問題規模(N)
運転回数
暴力法の実行時間は長い(ms)
分治法の運行時間は長い(ms)
120
10000
208
174
110
10000
178
157
100
10000
147
141
95
10000
133
131
94
10000
138
142
90
10000
124
142
80
10000
101
136
70
10000
79
109
観察によると、N=94の時に暴力法が実行されると、分治法より長い時間がかかります.つまり、この方程式の解n 0は性能交差点が94です.
ハイブリッド
問題の規模がn 0以下の場合は暴力アルゴリズムを採用し、n 0より大きい場合は分割アルゴリズムを採用し、性能の交差点を見てください.

ans MaxSubarray_mix(int A[], int low, int high) {
	if (high < CROSS) {
		return MaxSubarray_violent(A, low, high);
	}
	return MaxSubarray_divide(A, low, high);
}

私の分析:問題の規模がn 0以下の場合、混合法の運行時間は暴力法に等しいです.n 0以上の場合、運行時間は分治法に等しいです.関数画像から見れば、2関数の最小値にすぎないので、性能の交差点は変化しないと思います.この方法は比較的良いと思います.実際:混合法の運行時間が長くて不規則であることが分かりました.推測は混合法を置いているからです.最後にテストします.コンパイラは繰り返し動作の関数を最適化します.ランダム配列を固定配列に変えてテストしてください.