为何O(NlogN)分治算法与O(N²)暴力算法实测运行时间一致？

问题背景 #

编写了两个求解给定序列最大连续子序列和的函数maxSubSum2与maxSubSum3，实现与测试过程如下。

maxSubSum2() 实现说明 #

实现逻辑 #

• 遍历整个vector，每轮迭代设置子序列起始标记begin
• 对每个起始标记，逐位向后移动结束标记end
• 累加起止标记区间内的元素和，判断是否为当前最大值并更新

对应代码 #

int maxSubSum2(const std::vector<int> &v)
{
    int maxSum = 0;
    for(std::size_t begin = 0; begin < v.size(); ++begin)
    {
        int thisSum = 0;
        for(std::size_t end = begin; end < v.size(); ++end)
        {
            thisSum += v[end];
            if(thisSum > maxSum)
                maxSum = thisSum;
        }
    }
    return maxSum;
}

maxSubSum3() 实现说明 #

实现逻辑 #

• 该函数为递归分治函数maxSumRec()的驱动入口
• maxSumRec采用分治策略计算最大子序列和：最大子序列和仅可能出现在三个位置：左半区间、右半区间、跨越左右分界的区间（左半部分含分界点center的最大后缀和，加右半部分含分界点center+1的最大前缀和）

对应代码 #

int maxSubSum3(const std::vector<int> &v)
{
    return maxSumRec(v, 0, v.size() - 1);
}

int maxSumRec(const std::vector<int> &v, std::vector<int>::size_type left, std::vector<int>::size_type right)
{
    if(left == right)
        if(v[left] > 0)
            return v[left];
        else
            return 0;
    std::vector<int>::size_type center = (left + right) / 2;
    int maxLeftSum = maxSumRec(v, left, center);
    int maxRightSum = maxSumRec(v, center + 1, right);
    int maxLeftBorderSum = 0;
    int leftBorderSum = 0;
    for(std::vector<int>::size_type idx = center; idx < v.size(); --idx)
    {
        leftBorderSum += v[idx];
        if(leftBorderSum > maxLeftBorderSum)
            maxLeftBorderSum = leftBorderSum;
    }
    int maxRightBorderSum = 0;
    int rightBorderSum = 0;
    for(std::vector<int>::size_type idx = center + 1; idx <= right; ++idx)
    {
        rightBorderSum += v[idx];
        if(rightBorderSum > maxRightBorderSum)
            maxRightBorderSum = rightBorderSum;
    }
    return max3(maxLeftSum, maxRightSum, maxLeftBorderSum + maxRightBorderSum);
}

int max3(int n1, int n2, int n3)
{
    if(n1 >= n2 && n1 >= n3) return n1;
    if(n2 >= n1 && n2 >= n3) return n2;
    if(n3 >= n1 && n3 >= n2) return n3;
    return 0; // <--- Should never happen
}

初始复杂度判断与测试方案 #

按照初始理论分析：

• 最初误以为双层嵌套结构的maxSubSum2()时间复杂度为O(N)
• 认为采用分治策略的maxSubSum3()时间复杂度应为O(NlogN)

为验证性能差异，编写基于std::chrono的计时函数stopwatch()测量两个函数的实际运行时间：

void stopwatch(int (*maxSubSumN)(const std::vector<int>&), const std::vector<int> &v)
{
    std::chrono::time_point start = std::chrono::steady_clock::now();
    maxSubSumN(v);
    std::chrono::time_point end = std::chrono::steady_clock::now();
    std::chrono::duration<double> runtime = end - start;
    std::cout << std::fixed << std::setprecision(9) << std::left << std::setw(9) << runtime.count();
}

测试前生成两个vector容器small和big，分别填充不同规模、取值范围为[-50,50]的随机整数，测试代码如下：

int randInt()
{
    return std::rand() % 101 - 50;
}

void populate(std::vector<int> &v)
{
    for(int &i : v)
        i = randInt();
}

int main()
{
    std::srand(std::time(NULL));
    std::vector<int> small(1000);
    std::vector<int> big(10000);
    populate(small);
    populate(big);
    std::cout << "[OPTIMIZED BRUTE FORCE] \t: ";
    stopwatch(maxSubSum2, small);
    std::cout << std::endl;
    std::cout << "[OPTIMIZED BRUTE FORCE] \t: ";
    stopwatch(maxSubSum2, big);
    std::cout << std::endl;
    std::cout << "[DIVIDE AND CONQUER] \t\t: ";
    stopwatch(maxSubSum3, small);
    std::cout << std::endl;
    std::cout << "[DIVIDE AND CONQUER] \t\t: ";
    stopwatch(maxSubSum3, big);
    std::cout << std::endl;
    return 0;
}

异常现象与待解疑问 #

多次测试覆盖从10/100规模到1000/1000000规模的多组数据后，发现两个函数的执行时间几乎完全一致，存在以下疑问：

1. 对两个算法的时间复杂度计算是否存在错误？
2. maxSumRec的实现是否存在隐藏bug（尽管它可以返回正确结果）？
3. 代码实现中是否存在未考虑到的性能瓶颈？
4. 是否遗漏或误解了算法分析相关的知识点？

参考学习资料：《Data Structures and Algorithm Analysis in C++ (4th Edition)》

问题根因定位 #

最终定位问题根源为无符号整数溢出引发的循环边界错误，问题代码段如下：

for(std::vector<int>::size_type idx = center; idx < v.size(); --idx)

该循环本应从center向左遍历到当前递归区间的左边界left，但存在两处错误：

• 错误设置了循环终止条件
• idx为无符号size_type类型，递减到0后继续下溢为极大值，导致循环实际遍历到数组起始位置0

该bug使得单次递归调用的时间复杂度从O(right-left)变为O(n)，总递归调用次数为O(n)，最终分治算法的总时间复杂度退化为O(n²)，因此与暴力法运行时间几乎一致。

内容的提问来源于stack exchange，提问作者akaAbdullahMateen