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

御笔剑客

1. int solve(int left, int right)
   
2. {
   
3.         if(left == right)
   
4.                 return num[left];
   
5. 
   
6.         mid = (left + right) / 2;
   
7.         lans = solve(left, mid);
   
8.         rans = solve(mid + 1, right);
   
9. 
   
10.         sum = 0, lmax = num[mid], rmax = num[mid + 1];
    
11.         for(i = mid; i >= left; i--) {
    
12.                 sum += num[i];
    
13.                 if(sum > lmax) lmax = sum;
    
14.         }
    
15.         sum = 0;
    
16.         for(i = mid + 1; i <= right; i++) {
    
17.                 sum += num[i];
    
18.                 if(sum > rmax) rmax = sum;
    
19.         }
    
20. 
    
21.         ans = lmax + rmax;
    
22.         if(lans > ans) ans = lans;
    
23.         if(rans > ans) ans = rans;
    
24.         return ans;
    
25. }
    
26. 
    
27. int main(void)
    
28. {
    
29.         scanf("%d", &n);
    
30.         for(i = 1; i <= n; i++)
    
31.                 scanf("%d", &num[i]);
    
32. 
    
33.         printf("%d\n", solve(1, n));
    
34.         return 0;
    
35. }

复制代码

我算出了是这是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 这种折半的遍历