关于这个算法的时间复杂度

御笔剑客

int solve(int left, int right)
{
        if(left == right)
                return num[left];

        mid = (left + right) / 2;
        lans = solve(left, mid);
        rans = solve(mid + 1, right);

        sum = 0, lmax = num[mid], rmax = num[mid + 1];
        for(i = mid; i >= left; i--) {
                sum += num[i];
                if(sum > lmax) lmax = sum;
        }
        sum = 0;
        for(i = mid + 1; i <= right; i++) {
                sum += num[i];
                if(sum > rmax) rmax = sum;
        }

        ans = lmax + rmax;
        if(lans > ans) ans = lans;
        if(rans > ans) ans = rans;
        return ans;
}

int main(void)
{
        scanf("%d", &n);
        for(i = 1; i <= n; i++)
                scanf("%d", &num[i]);

        printf("%d\n", solve(1, n));
        return 0;
}

我算出了是这是O（n^2）的时间复杂度，但是感觉不对，应该怎么算呢？

claws0n

不会是 n^2。
一开始折半，logn
后面两个循环，但分别遍历的只有数组的一半，n
所以只有 n + logn，大欧只有 n

御笔剑客

claws0n 发表于 2018-9-17 20:48
不会是 n^2。
一开始折半，logn
后面两个循环，但分别遍历的只有数组的一半，n

那应该是O（nlogn）吧

claws0n

御笔剑客 发表于 2018-9-17 21:31
那应该是O（nlogn）吧

不会，递归在前面，if 左右相等，即只有一个元素时，返回，遍历只有一次。前面的递归感觉好费，其实就是第一个元素和 mid+1 吧

御笔剑客

claws0n 发表于 2018-9-17 22:04
不会，递归在前面，if 左右相等，即只有一个元素时，返回，遍历只有一次。前面的递归感觉好费，其实就是 ...

总时间应该是：T(n)=2T（n/2）+f(n) 吧

claws0n

御笔剑客 发表于 2018-9-17 22:05
总时间应该是：T(n)=2T（n/2）+f(n) 吧

我没这样算，反正你要的是上限。你这个算法会是 nlogn 吧？
你看 lans 是递归，所以不会往下走，直到 if，退出。才来执行 rans，同理...。之后才遍历，所以两者是独立的。
你的 mid 是局部变量吧？两个递归完后会变回 (1+n)/2

claws0n

御笔剑客 发表于 2018-9-17 22:05
总时间应该是：T(n)=2T（n/2）+f(n) 吧

看漏了，是 nlogn，但是计算的方式不像是那么简单。

御笔剑客

claws0n 发表于 2018-9-18 11:07
看漏了，是 nlogn，但是计算的方式不像是那么简单。

设执行时间为k次，然后多次迭代，k=log2n，应该就算出来是nlogn了

claws0n

御笔剑客 发表于 2018-9-18 14:59
设执行时间为k次，然后多次迭代，k=log2n，应该就算出来是nlogn了

对，如果说是看大体的话，但是我看了累加的次数，非常不对称，并不是单纯的 2 4 8 这种折半的遍历