算法導論第四章練習題4.1-1

題目描述

• 在你的計算機上實作最大子數組問題的暴力算法和遞歸算法。請指出多大的問題規模n0是性能交叉點——從此之後遞歸算法将擊敗暴力算法？

代碼

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <assert.h>

using namespace std;

void generateRandomArray(int arr[], int n, int rangeL, int rangeR);//生成包含n個數的随機數組
vector<int> bruteSearch(int arr[], size_t n);//暴力搜尋算法
vector<int> recursiveSearch(int arr[], int low, int high);//遞歸算法
vector<int> crossSubarray(int arr[], int low, int mid, int high);//用于求解遞歸算法中最大子字元串跨越中點的情況

int main() {
	constexpr unsigned n = 1000000;
	cout << "輸入規模為：" << n << endl;
	static int arr[n];
	generateRandomArray(arr, n, -100, 100);

	clock_t start2, finish2;
	vector<int> ans2;
	start2 = clock();
	ans2 = recursiveSearch(arr, 0, n - 1);
	finish2 = clock();
	cout << "The answer of recursive search is:" << endl;
	for (auto &c : ans2) {
		cout << c << endl;
	}
	cout << "運作時間為：" << (double)(finish2 - start2) / CLOCKS_PER_SEC << endl;
	cout << "---------------------------------------" << endl;

	clock_t start1, finish1;
	vector<int> ans1;
	start1 = clock();
	ans1 = bruteSearch(arr, n);
	finish1 = clock();
	cout << "The answer of brute search is:" << endl;
	for (auto &c : ans1) {
		cout << c << endl;
	}
	cout << "運作時間為：" << (double)(finish1 - start1) / CLOCKS_PER_SEC << endl;
	cout << "---------------------------------------" << endl;
};

void generateRandomArray(int arr[], int n, int rangeL, int rangeR) {
	assert(rangeL <= rangeR);
	// srand(time(NULL)); // 随機種子
	for (int i = 0; i < n - 1; i++)
		arr[i] = rand() % (rangeR - rangeL + 1) + rangeL;
}

vector<int> bruteSearch(int arr[], size_t n) {
	int max_sum = INT_MIN;
	int left = 0;
	int right = 0;
	for (size_t i = 0; i != n - 1; ++i) {
		int sum = 0;
		for (size_t j = i; j != n; ++j) {
			sum += arr[j];
			if (sum > max_sum) {
				max_sum = sum;
				left = i;
				right = j;
			}
		}
	}
	return { left, right, max_sum};
}

vector<int> crossSubarray(int arr[], int low, int mid, int high) {
	int left_sum = INT_MIN;
	int max_left = 0;
	int max_right = 0;
	int sum = 0;
	for (int i = mid; i >= low; --i) {
		sum += arr[i];
		if (sum > left_sum) {
			left_sum = sum;
			max_left = i;
		}
	}
	int right_sum = INT_MIN;
	sum = 0;
	for (int i = mid + 1; i <= high; ++i) {
		sum += arr[i];
		if (sum > right_sum) {
			right_sum = sum;
			max_right = i;
		}
	}
	return { max_left, max_right, left_sum + right_sum };
}

vector<int> recursiveSearch(int arr[], int low, int high) {
	if (high == low) {
		return { low, high, arr[low] };
	}
	else {
		int mid = (low + high) / 2;
		vector<int> vec_left = recursiveSearch(arr, low, mid);
		vector<int> vec_right = recursiveSearch(arr, mid+1, high);
		vector<int> vec_cross = crossSubarray(arr, low, mid, high);
		if (vec_left[2] >= vec_right[2] && vec_left[2] >= vec_cross[2])
			return vec_left;
		else if (vec_right[2] >= vec_left[2] && vec_right[2] >= vec_cross[2])
			return vec_right;
		else return vec_cross;
	}
}
           

• 實驗發現，n<10000時，暴力搜尋算法性能更好，n=10000時，兩種算法性能相當，n>10000時，遞歸算法開始展現出明顯優勢
• 實驗結果如下;