c++分别设计时间复杂度为θ(n²)、θ(nlogn)和 θ(n)的多项式时间算法求解最大和子数组问题。并随机产生规模为n=1000,10000.100000， 1000000的输入实例。输出最大子数组的左右下标和其元素之和。并比较各算法在各输入实例规模所运行时间。给出完整连续代码

### C++ 实现最大和子数组问题的不同时间复杂度算法 以下是三种不同时间复杂度的解决方案：\( \theta(n^2) \), \( \theta(n\log n) \), 和 \( \theta(n) \)，并附带随机生成输入实例的功能，用于比较它们在不同规模下的运行时间。 --- #### 方法一：暴力解法 (\( O(n^2) \)) 通过两重循环枚举所有可能的子数组，并记录其中的最大和及其对应的左右边界。 ```cpp #include <iostream> #include <vector> #include <ctime> using namespace std; pair<int, pair<int, int>> maxSubArrayBruteForce(const vector<int>& nums) { int maxSum = INT_MIN; int startIdx = 0, endIdx = 0; for (int i = 0; i < nums.size(); ++i) { // Outer loop: starting index of subarray int currentSum = 0; for (int j = i; j < nums.size(); ++j) { // Inner loop: ending index of subarray currentSum += nums[j]; if (currentSum > maxSum) { maxSum = currentSum; startIdx = i; endIdx = j; } } } return make_pair(maxSum, make_pair(startIdx, endIdx)); } ``` 此方法的时间复杂度为 \( O(n^2) \)[^1]，因为它涉及双重嵌套循环来遍历所有的子数组组合。 --- #### 方法二：分治法 (\( O(n\log n) \)) 利用递归将数组分为左半部分、右半部分以及跨越中间的部分，分别求解这三个区域中的最大子数组和。 ```cpp int crossMaxSum(const vector<int>& nums, int low, int mid, int high) { int leftSum = INT_MIN, sum = 0; int maxLeft = mid; for (int i = mid; i >= low; --i) { sum += nums[i]; if (sum > leftSum) { leftSum = sum; maxLeft = i; } } int rightSum = INT_MIN, sumRight = 0; int maxRight = mid + 1; for (int i = mid + 1; i <= high; ++i) { sumRight += nums[i]; if (sumRight > rightSum) { rightSum = sumRight; maxRight = i; } } return leftSum + rightSum; } pair<int, pair<int, int>> maxSubArrayDivideAndConquerHelper(const vector<int>& nums, int low, int high) { if (low == high) { return make_pair(nums[low], make_pair(low, high)); // Base case: only one element } else { int mid = (low + high) / 2; auto leftResult = maxSubArrayDivideAndConquerHelper(nums, low, mid); auto rightResult = maxSubArrayDivideAndConquerHelper(nums, mid + 1, high); int crossSum = crossMaxSum(nums, low, mid, high); if ((leftResult.first >= rightResult.first) && (leftResult.first >= crossSum)) { return leftResult; } else if ((rightResult.first >= leftResult.first) && (rightResult.first >= crossSum)) { return rightResult; } else { return make_pair(crossSum, make_pair(-1, -1)); // Cross-sum indices not needed here } } } pair<int, pair<int, int>> maxSubArrayDivideAndConquer(const vector<int>& nums) { return maxSubArrayDivideAndConquerHelper(nums, 0, nums.size() - 1); } ``` 该方法基于 Master 定理[^2]得出其时间复杂度为 \( O(n\log n) \). --- #### 方法三：动态规划 (\( O(n) \)) 采用 Kadane's Algorithm 来线性扫描整个数组，在一次遍历中找到全局最优解。 ```cpp pair<int, pair<int, int>> maxSubArrayKadane(const vector<int>& nums) { int maxSoFar = INT_MIN, maxEndingHere = 0; int start = 0, end = 0, s = 0; for (int i = 0; i < nums.size(); ++i) { maxEndingHere += nums[i]; if (maxSoFar < maxEndingHere) { maxSoFar = maxEndingHere; start = s; end = i; } if (maxEndingHere < 0) { maxEndingHere = 0; s = i + 1; } } return make_pair(maxSoFar, make_pair(start, end)); } ``` 由于只有一层循环完成全部工作，因此这种方法的时间复杂度为 \( O(n) \). --- #### 测试框架与性能对比 下面是一个完整的测试框架，它会自动生成指定范围内的随机数据集，并测量上述三个函数的实际执行速度： ```cpp void testAlgorithms(int size) { srand(time(NULL)); cout << "Generating random array with size: " << size << endl; vector<int> data(size); for (auto& num : data) { num = rand() % 100 - 50; // Random numbers between [-50, 50] } clock_t begin_bruteforce = clock(); auto resultBF = maxSubArrayBruteForce(data); clock_t end_bruteforce = clock(); double time_spent_bf = static_cast<double>(end_bruteforce - begin_bruteforce) / CLOCKS_PER_SEC; clock_t begin_divconq = clock(); auto resultDC = maxSubArrayDivideAndConquer(data); clock_t end_divconq = clock(); double time_spent_dc = static_cast<double>(end_divconq - begin_divconq) / CLOCKS_PER_SEC; clock_t begin_kadane = clock(); auto resultKA = maxSubArrayKadane(data); clock_t end_kadane = clock(); double time_spent_ka = static_cast<double>(end_kadane - begin_kadane) / CLOCKS_PER_SEC; cout << "\nResults:\n"; cout << "Brute Force Result: Sum=" << resultBF.first << ", Indices=(" << resultBF.second.first << "," << resultBF.second.second << "), Time Taken=" << fixed << time_spent_bf << "s\n"; cout << "Divide and Conquer Result: Sum=" << resultDC.first << ", Indices=(" << resultDC.second.first << "," << resultDC.second.second << "), Time Taken=" << fixed << time_spent_dc << "s\n"; cout << "Kadane's Algorithm Result: Sum=" << resultKA.first << ", Indices=(" << resultKA.second.first << "," << resultKA.second.second << "), Time Taken=" << fixed << time_spent_ka << "s\n"; } int main() { const int sizes[] = {100, 1000, 10000}; // Example input scales to compare performance. for(auto sz : sizes){ testAlgorithms(sz); } return 0; } ``` 以上代码展示了如何创建具有不同长度的随机数组，并评估每种策略的表现差异。注意实际耗时取决于硬件环境等因素。 ---