这个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)

- Bunny Rabbit

---

这是一道考试中出现的客观题，提供的选项为1.O(1) 2.O(n) 3.O(n!) 4.O(n^n)。 - Bunny Rabbit

@Bunny Rabbit，也许你的老师不熟悉O符号，但3.O(n!)和4.O(n^n)都是正确的，它们也可以表示为O(2^n)，实际上是Teta(2^n)。 - Saeed Amiri

我想重点是选择最紧密的边界。 - Bunny Rabbit

你没有为O(n!)提供任何解释 :( :( - Bunny Rabbit

@Bunny Rabbit，请看我的更新。 - Saeed Amiri

Answer 1

假设f为算法的运行时间，则其复杂度为Θ(2^n)：

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)

- Saeed Amiri

---

实际上，沃尔夫拉姆阿尔法告诉我它确切地是2^n，但是嘿，细节 :P - Juan

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返回一个double？它总是返回一个整数，而不是一个double。

以下是更好的版本，具有微小的优化！: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;
    }
}

- Thomas Havlik

---

为什么foo返回double？因为它是double。（重言反复胜利！） - Mateen Ulhaq

将sum强制转换为int将得到完全相同的值。使用int而不是double可以占用4个字节的内存，而不是8个字节。i增加1，与n进行比较，因此该函数始终以整数作为参数递归调用。除非您正在处理超级负数或正数，否则它永远不需要返回double。 - Thomas Havlik

当然，对于负数有一个例外。它不会进行递归调用，因为 i 始终大于 n。 - Thomas Havlik

Answer 3

你本可以更清楚一些... 咕哝咕哝

<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_called = 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));
}

- Mateen Ulhaq

---

不错的答案，但完全离题了。 - Juan

@Juan，原帖不够清晰...至少在我第一次看到这个问题时是这样的。大多数情况下，我只看到了代码和“你能解释一下吗”，或者类似的内容。 - Mateen Ulhaq

Answer 4

这个函数由多个部分组成。

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

下一部分是 for(i=0; i<n; i++) 循环。由于循环从 0..n，所以它是 O(n)

然后是递归，对于每个数字在 n 中，您再次运行该函数。在那个函数中又有循环和下一个函数。依此类推...

为了弄清楚它将会是什么，我建议您在循环内添加一个全局计数器，这样您就可以看到它针对某个数字执行了多少次。

- Wolph

---

查看我的答案以获取执行次数。 - Mateen Ulhaq