具有递归调用f(n/2)和f(n - 2)的函数的时间复杂度？

Question

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

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

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

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

Answer 1

我认为它是指数级的。为什么？每个 f(n) 都会导致调用 f(n/2) 和 f(n-2)。

检查此问题以了解详细信息：

斐波那契数列的计算复杂度

这就是斐波那契顺序的复杂性。您的功能结构类似。