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

### 不同时间复杂度的最大和子数组算法实现 最大和子数组问题是经典的计算机科学问题之一，目标是从给定的一维整数数组中找到具有最大和的连续子数组。以下是三种不同时间复杂度（\( \theta(n^2) \), \( \theta(n\log n) \), 和 \( \theta(n) \)）的 C++ 实现及其运行性能测试方法。 --- #### 1. 时间复杂度为 \( \theta(n^2) \) 的暴力解法 该算法通过两层嵌套循环枚举所有可能的子数组并计算其总和来解决问题。虽然简单直观，但在大规模数据集上的表现较差。 ```cpp #include <iostream> #include <vector> using namespace std; int maxSubArrayBruteForce(const vector<int>& nums) { int maxSum = INT_MIN; for (size_t i = 0; i < nums.size(); ++i) { // Start index of subarray int currentSum = 0; for (size_t j = i; j < nums.size(); ++j) { // End index of subarray currentSum += nums[j]; if (currentSum > maxSum) { maxSum = currentSum; } } } return maxSum; } ``` 上述代码的时间复杂度为 \( O(n^2) \)[^1]，因为它涉及两个嵌套循环遍历整个数组中的每一对起点和终点索引组合。 --- #### 2. 时间复杂度为 \( \theta(n\log n) \) 的分治法 此方法基于递归的思想，将原问题分解成较小的子问题求解后再合并结果。具体来说，对于任意区间 `[low, high]`，可以将其划分为三个部分：左半边的最佳子数组、右半边的最佳子数组以及跨越中间位置的最佳子数组。 ```cpp #include <climits> // Helper function to find the maximum crossing sum w.r.t mid point. int maxCrossingSum(const vector<int>& nums, int low, int mid, int high) { int leftSum = INT_MIN; int total = 0; for(int i = mid; i >= low; --i){ total += nums[i]; if(total > leftSum){ leftSum = total; } } int rightSum = INT_MIN; total = 0; for(int i = mid + 1; i <= high; ++i){ total += nums[i]; if(total > rightSum){ rightSum = total; } } return leftSum + rightSum; } // Recursive implementation using divide and conquer strategy. int maxSubArrayDivideAndConquer(const vector<int>& nums, int low, int high) { if(low == high){ // Base case with one element only. return nums[low]; } int mid = low + (high - low)/2; /* Return maximum of following three possible cases */ return max({maxSubArrayDivideAndConquer(nums, low, mid), maxSubArrayDivideAndConquer(nums, mid+1, high), maxCrossingSum(nums, low, mid, high)}); } int maxSubArrayDC(vector<int> &nums){ return maxSubArrayDivideAndConquer(nums, 0, static_cast<int>(nums.size())-1); } ``` 这段程序实现了分治策略，整体时间复杂度为 \( O(n\log n) \)[^3]。 --- #### 3. 时间复杂度为 \( \theta(n) \) 的动态规划解法 Kadane's Algorithm 是一种高效的线性扫描技术，能够在线性时间内解决这个问题。核心思想是在一次迭代过程中维护当前最优解的同时更新全局最佳解。 ```cpp int maxSubArrayKadane(const vector<int>& nums) { int maxSoFar = nums[0], currMax = nums[0]; for(size_t i=1;i<nums.size();++i){ currMax = max(nums[i], currMax + nums[i]); maxSoFar = max(maxSoFar, currMax); } return maxSoFar; } ``` 这种解决方案仅需单次遍历即可完成任务，因此它的渐近时间为常量因子乘积形式即 \( O(n) \)[^2]。 --- #### 性能测试框架 为了对比以上三种方法的实际执行速度差异，在不同的输入规模下测量各自的耗时是非常必要的： ```cpp #include <chrono> #include <random> #include <iomanip> void testPerformance() { default_random_engine generator; uniform_int_distribution<int> distribution(-100, 100); const size_t MAX_SIZE = 1e5; vector<vector<int>> datasets{}; cout << fixed << setprecision(6); auto generateDataset = [&](size_t N)->vector<int>{ vector<int> dataset(N); for(auto& num : dataset){ num = distribution(generator); } return dataset; }; for(size_t sz=10;sz<=MAX_SIZE;sz*=10){ datasets.push_back(generateDataset(sz)); } for(auto& data : datasets){ double t_bruteforce = measureTime([&]{return maxSubArrayBruteForce(data);}); double t_divconq = measureTime([&]{return maxSubArrayDC(data);}); double t_kadane = measureTime([&]{return maxSubArrayKadane(data);}); cout << "Size:" << setw(8)<<data.size()<<" | BF:"<<setw(9)<<t_bruteforce<<"s" <<"| DC:"<<setw(9)<<t_divconq<<"s"<<"| KA:"<<setw(9)<<t_kadane<<"s\n"; } } template<typename FuncT> double measureTime(FuncT func){ auto start = chrono::steady_clock::now(); func(); auto end = chrono::steady_clock::now(); return chrono::duration<double>(end-start).count(); } ``` 这里定义了一个通用函数 `measureTime()` 来封装计时逻辑，并利用标准库 `<chrono>` 提供的功能精确记录每次调用所需花费的真实秒数。 ---