时间戳

首页 > 解决方案 > 这个函数的时间和空间复杂度是多少

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

问题描述

我无法解决我遇到的 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）。从这一点开始，我不知道该怎么做。

请解释你解决它的方式。非常感谢 ：）

标签： c

解决方案

时间：

由于at 每次递归调用，您已经计算出g3(n)递归时间。这也意味着基本情况( )在最终返回之前将大致平方数倍。log_2 nn/22log_2 n

然后的返回值g3(n)是 ~ 2^(2^log_2 n)，它简化为 ~ 2^n。

要弄清楚 中发生了什么g3(g3(n))，我们可以计算出内部调用返回的g3(k)where中发生了什么。你已经知道递归时间就像内部调用一样。因此，如果我们用我们的内部结果替换，我们会得到简化为的递归调用。因此，外部调用递归时间。k = 2^ng3(n)g3(k)log_2 kklog_2 (2^n)ng3(g3(n))n

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

因此，f3(n)需要O(n)时间。

空间：

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

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

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

执行过程中同时分配的最大堆栈帧数是多少？如果你能回答这个问题，那么你就可以计算出分配的帧数作为n空间复杂度的函数。最后的结果留给大家看。

如果您无法解决某事，请将其分解为您可以解决的较小问题。每次你解决一个小问题时，看看你如何使用结果来简化大问题。

推荐阅读