计算空间复杂度

Question

我得到了这段代码的样本，我不确定这里的空间复杂度是多少。

void f1(int n){
    int b = 2;
    while (n >= 1){
        b *= b;
        n /= 2;
    }
    free(malloc(b));
}

就循环而言，它运行log(n)次，但变量b呈指数增长。

这就是为什么我不知道发生了什么。

感谢您在这方面的帮助:)

Answer 1

首先，如果您按原样运行它，那么您将获得内存溢出，因为大多数数值数据类型的内存有限(例如，32位)。因此，我假设您在图灵机上运行该算法，图灵机是一个理想化的计算机模型。在这种情况下，n将比b的最后一个值小得多。此外，我假设您的目标是计算b的最后一个值，因此您需要在内存末尾写入b的值(例如二进制)。记住这些，你只需要使用足够的空间，在内存(磁带)上记录所有的b值。你不需要太多的内存，只需要记录最后b取的值。因此，你的空间复杂度是$O(2^{2^{log_2(n)}})$，简单地说就是O(2^n)