一个递归函数调用自己N次少一个的时间复杂度是多少？

Question

这种结构的递归函数的时间复杂度是多少

void f(int n)
{
    if (n == 0)
        return;
    for (int i = n; i >= 1; --i)
    {
        // something O(1)
        f(n - i);
    }
}

我的想法是遵循

T(n) = T(0) + ... + T(n-2) + T(n-1) = (T(0) + ... + T(n-2)) + T(n-1) = T(n-1) + T(n-1) = 2T(n-1)

所以我们会说 O(2^n-1)？

或者是

T(n) = T(0) * ... * T(n-1)

Answer 1

看来你的分析很有道理。

如有疑问，您可以进行测量。如果复杂度真的是 O(2^n) 那么你可以计算内循环执行的频率，并且为了增加 n 计数除以 2^n 应该收敛：

#include <iostream>

struct foo {
    int counter = 0;
    void f(int n) {
        if (n == 0)
            return;
        for (int i = n; i >= 1; --i) {
            ++counter;
            f(n - i);
        }
    }
};

int main() {
    for (int i=0;i < 4;++i) {
        long int n = 2<<i;
        foo f;
        f.f(n);        
        std::cout << n << " " << (2<<n) << " " << f.counter / static_cast<double>(2<<n)  << "\n";
    }
}

输出为：

2 8 0.375
4 32 0.46875
8 512 0.498047
16 131072 0.499992

请注意，此测量值不能证明您的分析是正确的。虽然计数似乎收敛到 0.5 并且测量不能伪造你的分析。计数似乎在 2^n-1 左右，只是对于复杂性而言，常数因子 2 并不重要，您可以将其写为 O(2^n).

PS：考虑算法时，复杂性很有趣。在考虑具体实施时，情况有些不同。请注意，编写的函数可以优化为等效的 void f(int) {} ，这显然不是 O(2^n).

一个递归函数调用自己N次少一个的时间复杂度是多少？

What is the time complexity of a recursive function that calls itself N times with one less?

c++

recursion

time-complexity