c - 为 F(n)=0.5F(n-1) 编写函数

Question

let F(n)=0.5F(n-1) and F(0)=1

a. write a function fun1, a recursive function to evaluate the n's term

b. write a function fun2, a non recursive function to evaluate the n's term

c. what is the time complexity of fun1 and from which n term it will be better to use fun1 vs fun2 regarding space complexity

通常，该函数评估序列 {1,1/2,1/4,1/8,...} 的 n 项

一种。

 double fun1( int n ){
    if (n == 0)
        return 1;
    else
        return 0.5*fun1(n-1);
}

湾

double fun2( int n ){
    double sum = 1, i;
    for (i=0 ; i < n; i++)
        sum=sum*(0.5);
    return sum;
}

C。直观地和数学地使用等比数列的和，我们可以证明它是 O(n)

还有另一种方法吗？

如何解决空间复杂度？

Answer 1

虽然您的 fun1 和 fun2 版本具有不同的空间复杂度，但它们的时间复杂度为 O(n)。

但是，非递归函数也可以写成:

#import <math.h>

double fun2(int n) {
    return pow(0.5, n);
}

该函数的空间和时间复杂度为 O(1)，并且对于大多数 n(可能 n > 5)会更有效。

至于最初的问题:这非常棘手，因为它取决于编译器优化:

一个简单的 fun1 实现的空间复杂度为 O(n)，因为 fun1(n) 的调用将具有 n 的递归深度，因此需要堆栈上的 n 个调用帧。在大多数系统上，它只能工作到某个 n。然后您会收到 Stack Overflow 错误，因为堆栈的大小有限。

优化编译器会识别出它是一个尾递归函数，并将其优化为非常接近 fun2 的函数，它的空间复杂度为 O(1)，因为它使用固定数量的变量，其大小与 n 无关，并且没有递归。