关于这个算法的时间复杂度
int solve(int left, int right){
if(left == right)
return num;
mid = (left + right) / 2;
lans = solve(left, mid);
rans = solve(mid + 1, right);
sum = 0, lmax = num, rmax = num;
for(i = mid; i >= left; i--) {
sum += num;
if(sum > lmax) lmax = sum;
}
sum = 0;
for(i = mid + 1; i <= right; i++) {
sum += num;
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);
printf("%d\n", solve(1, n));
return 0;
}
我算出了是这是O（n^2）的时间复杂度，但是感觉不对，应该怎么算呢？ 不会是 n^2。
一开始折半，logn
后面两个循环，但分别遍历的只有数组的一半，n
所以只有 n + logn，大欧只有 n claws0n 发表于 2018-9-17 20:48
不会是 n^2。
一开始折半，logn
后面两个循环，但分别遍历的只有数组的一半，n
那应该是O（nlogn）吧 御笔剑客 发表于 2018-9-17 21:31
那应该是O（nlogn）吧
不会，递归在前面，if 左右相等，即只有一个元素时，返回，遍历只有一次。前面的递归感觉好费，其实就是第一个元素和 mid+1 吧 claws0n 发表于 2018-9-17 22:04
不会，递归在前面，if 左右相等，即只有一个元素时，返回，遍历只有一次。前面的递归感觉好费，其实就是 ...
总时间应该是：T(n)=2T（n/2）+f(n) 吧 御笔剑客 发表于 2018-9-17 22:05
总时间应该是：T(n)=2T（n/2）+f(n) 吧
我没这样算，反正你要的是上限。你这个算法会是 nlogn 吧？
你看 lans 是递归，所以不会往下走，直到 if，退出。才来执行 rans，同理...。之后才遍历，所以两者是独立的。
你的 mid 是局部变量吧？两个递归完后会变回 (1+n)/2 御笔剑客 发表于 2018-9-17 22:05
总时间应该是：T(n)=2T（n/2）+f(n) 吧
看漏了，是 nlogn，但是计算的方式不像是那么简单。 claws0n 发表于 2018-9-18 11:07
看漏了，是 nlogn，但是计算的方式不像是那么简单。
设执行时间为k次，然后多次迭代，k=log2n，应该就算出来是nlogn了 御笔剑客 发表于 2018-9-18 14:59
设执行时间为k次，然后多次迭代，k=log2n，应该就算出来是nlogn了
对，如果说是看大体的话，但是我看了累加的次数，非常不对称，并不是单纯的 2 4 8 这种折半的遍历
页:
[1]