这个c函数的复杂度是多少

Question

以下 c 函数的复杂度是多少？

double foo (int n) {
    int i;
    double sum;
    if (n==0) return 1.0;
    else {
        sum = 0.0;
        for (i =0; i<n; i++)
        sum +=foo(i);
        return sum;
    }
}

请不要只是发布复杂性，你能帮助我理解如何去做吗？

编辑：这是考试中提出的客观问题，提供的选项是 1.O(1) 2.O(n) 3.O(n!) 4.O(n^n)

Answer 1

它是 θ(2^n)（假设 f 是我们算法的运行时间）：

f(n) = f(n-1) + f(n-2) + ... + 1
f(n-1) = f(n-2) + f(n-3) + ...
==> f(n) = 2*f(n-1), f(0) = 1
==> f(n) is in O(2^n)

实际上，如果我们忽略常量操作，则确切的运行时间是 2ⁿ。

另外，在您写的这是一次考试的情况下，O(n!) 和 O(n^n) 都是正确的，其中最接近 θ(2^n) 的答案是 O(n!)，但如果我是学生，我会标记它们两个:)

---

O(n!) 的解释：

for all n >= 1: n! = n(n-1)...*2*1 >= 2*2*2*...*2 = 2^(n-1) ==>
2 * n! >= 2^n ==> 2^n is in O(n!),
Also n! <= n^n for all n >= 1 so n! is in O(n^n)

So O(n!) in your question is nearest acceptable bound to Theta(2^n)

Answer 2

其一，它的编码很差:)

double foo (int n) {         // foo return a double, and takes an integer parameter
    int i;                   // declare an integer variable i, that is used as a counter below
    double sum;              // this is the value that is returned
    if (n==0) return 1.0;    // if someone called foo(0), this function returns 1.0
    else { // if n != 0
        sum = 0.0;           // set sum to 0
        for (i =0; i<n; i++) // recursively call this function n times, then add it to the result
        sum +=foo(i);
        return sum;          // return the result
    }
}

您调用 foo() 的次数总共类似于 n^n （将 n 向下舍入到最接近的整数），

例如：

foo(3) 将被调用 3^3 次。

祝你好运，圣诞快乐。

编辑：哎呀，刚刚更正了一些内容。为什么 foo 返回双精度值？它将始终返回一个整数，而不是双精度数。

这将是一个更好的版本，带有微优化！ ：D

int foo(int n)
{
    if(n==0) return 1;
    else{
        int sum = 0;
        for(int i = 0; i < n; ++i)
        sum += foo(i);
        return sum;
    }
}

Answer 3

你本来可以更清楚一点... grumble grumble

<n = ?> : <return value> : <number of times called>
n = 0 : 1 : 1
n = 1 : 1 : 2
n = 2 : 2 : 4
n = 3 : 4 : 8
n = 4 : 8 : 16
n = 5 : 16 : 32
n = 6 : 32 : 64
n = 7 : 64 : 128
n = 8 : 128 : 256
n = 9 : 256 : 512
n = 10 : 512 : 1024

number_of_times_known = pow(2, n-1);

让我们尝试输入输入，好吗？

使用此代码：

#include <iostream>

double foo (int n) {
    int i;
    double sum;
    if (n==0) return 1.0;
    else {
        sum = 0.0;
        for (i =0; i<n; i++)
        sum +=foo(i);
        return sum;
    }
}


int main(int argc, char* argv[])
{
    for(int n = 0; 1; n++)
    {
       std::cout << "n = " << n << " : " << foo(n);
       std::cin.ignore();
 }

    return(0);
}

我们得到：

n = 0 : 1
n = 1 : 1
n = 2 : 2
n = 3 : 4
n = 4 : 8
n = 5 : 16
n = 6 : 32
n = 7 : 64
n = 8 : 128
n = 9 : 256
n = 10 : 512

因此，它可以简化为：

double foo(int n)
{
    return((double)pow(2, n));
}

Answer 4

该函数由多个部分组成。

第一个复杂性是 if(n==0)return 1.0;，因为它只生成一次运行。那将是O(1)。

下一部分是 for(i=0; i0..n 开始循环，所以它是 O(n)

比有递归，对于 n 中的每个数字，您都运行该函数再次。在该函数中再次循环，以及下一个函数。等等...

为了弄清楚它会是什么，我建议您在循环内部添加一个全局计数器，以便您可以看到它针对特定数量执行了多少次。