论递归的复杂度怎么算

回复帖子

@FullBT 2020-11-22 10:30 回复

类似以这个代码

#include <iostream>

using namespace std;

const int N = 1e6 + 7;

int n;

int a[N];

int sum[N << 2];

void build(int depth, int l, int r) {
    if (l == r) {
        sum[depth] = a[l];
        return ;
    }
    int mid = (l + r) >> 1;
    build(depth << 1, l, mid);//遍历左儿子 
    build(depth << 1 | 1, mid + 1, r);//遍历右儿子 
    sum[depth] = sum[depth << 1] + sum[depth << 1 | 1];//递归返回每层的值 
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i ++)
        cin >> a[i];
    build(1, 1, n);//层数,左右区间的端点 
    return 0;
}

他的复杂度多少

@Krystallos 2020-11-22 10:38 回复 举报

@FullBT 设进入一层递归时 $r - l + 1 = a$(即区间长度为 $a$)
那么时间复杂度 $T(a) = T\left( \left\lfloor \dfrac{a}{2}\right\rfloor \right) + T\left(\left\lceil \dfrac{a}{2} \right\rceil\right)$
边界为 $T(1) = 1$
所以 $T(a) = O(a)$
最上层递归 $a = n$
所以总复杂度是 $T(n) = O(n)$

@BlankAo  2020-11-22 10:38 回复 举报

因为你相当于把整棵二叉树都遍历了,而叶子节点数量是n,所以总的递归调用数量大约是nX2,就是O(n)

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。