这个函数的时间和空间复杂度是多少？

Question

我无法用C来解决这个时间和空间的复杂性。这就是问题所在：

计算函数f3的时间和空间复杂度：

double g3(double n) 
{
    if (n<=1)
    return 2;
    double temp = g3(n/2);
    return temp*temp;
}
double f3(double n){
    return g3(g3(n));
}

计算出g3的时间复杂度为O(logn)，其返回值为2^2^n-1 (对于n >= 1)。从现在起，我不知道该怎么做。

请解释一下你解决这个问题的方法。(非常感谢:)

Answer 1

时间：

您已经计算出，由于每次递归调用的g3(n)都是n/2，所以n/2会在log_2 n时间内递归。这也意味着，在基箱 (2)最终返回之前，大约要对其进行log_2 n平方。

g3(n)的返回值为~2^(2^log_2 n)，从而简化为~2^n。

为了计算g3(g3(n))中正在发生的事情，我们可以计算出g3(k)中发生了什么，其中k = 2^n是由内部g3(n)调用返回的。您已经知道，g3(k)像内部调用一样递归log_2 k时间。因此，如果用内部结果替换k，就会得到log_2 (2^n)递归调用，从而简化为n。因此，g3(g3(n))中的外部调用会递归n时间。

现在我们可以计算出总时间复杂度。首先，它需要O(log n)步骤来计算g3(n)。其次，它需要O(n)步骤来计算出g3(2^n)。因此，g3(g3(n))的总时间复杂度是内部+外部或O(log n) + O(n)，其中O(n)占主导地位。

因此，O(n) f3(n)采用time。

空间：

为了计算出使用了多少空间，我们需要考虑

1. 在我们的程序中，内存在哪里分配？
2. 作为n函数分配的最大内存量是多少？

我们没有任何占用内存的数组，因此我们最关心的是分配给每个函数调用的堆栈框架的内存。每次调用g3(n)时，都会分配一些内存来存储局部变量和其他数据。每次g3(n)返回时，该内存都会被释放，并可用于其他事情。

在执行过程中，同时分配的堆栈帧的最大数量是多少？如果您能够回答这个问题，那么您就可以计算出作为n函数分配的帧数，从而计算出空间复杂性。我会把最后的结果留给你去辨别。

如果你不能解决某件事，就把它分解成你能解决的小问题。每次解决一个小问题时，看看如何使用结果来简化大问题。