小编Cae*_*r23的帖子

我有这个功能,想知道时间的复杂性:

int f2(int n) {
    if(n<2) return 1;
    return f2(n/2)+f2(n-2);
}

我使用伸缩展开法计算其运行时间为O(n ²).它是否正确？

编辑:重新考虑之后,我发现这个函数有一个类似于mergesort的结构,它具有复杂度Θ(n log n).那是对的吗？