递归关系中的混淆。时间复杂度将为O（n）或O（nlogn）

Question

重复将如上所述，为T（n）= 2T（n / 2）+ O（1）。 f（n）如何是O（1）而不是O（n）。我们可以只分割而没有合并来划分和同意吗？即使在功能上看不到合并，我也不会不考虑合并而无法进行分析。

    //mx (largest sum of this subarray), 
    //lmx(largest sum starting from the left most element), 
    //rmx(largest sum ending with the right most element), 
    //sum(the sum of the total subarray).
    void maxSubArray(vector<int>& nums, int l, int r,
    int& mx,int& lmx, int& rmx, int& sum) {         
    if (l == r) {
        mx = lmx = rmx = sum = nums[l];
    }
    else {
        int m = (l + r) / 2;
        int mx1, lmx1, rmx1, sum1;
        int mx2, lmx2, rmx2, sum2;
        maxSubArray(nums, l, m, mx1, lmx1, rmx1, sum1);
        maxSubArray(nums, m + 1, r, mx2, lmx2, rmx2, sum2);
        mx = max(max(mx1, mx2), max(rmx1 + lmx2,sum1+sum2);
        lmx = max(lmx1, sum1 + lmx2);
        rmx = max(rmx2, sum2 + rmx1);
        sum = sum1 + sum2;
    }
}

Answer 1

因为长度vector的n仅被迭代一次而不是两次，所以，这给您带来了O(n)的复杂性。而max函数不会循环通过任何东西，并且复杂度O(1)等于您提到的1（可以忽略）因此，当您使用多个时，最终答案将是O(n)您代码中的函数，而不是仅考虑到磨碎的复杂性。

此外，您可以使用数学替换方法从您提供的递归表达式中获取答案。我可以告诉你替代方法。如果您想解决此问题，请在评论中让我知道。