查找此程序的时间和 space 复杂度

Question

    def g3(n):
        s = 0
        i = 1
        while i < n:
            i *= 2
            s += i
        return s
    
    def f3(n):
        s = []
        i = 2
        while (i < n):
            s.append(g3(i))
            i *= i
        return s

我正在尝试计算函数 f3 的时间和 space 复杂度，我得到了一些错误的答案，我不知道我的错误在哪里，最后的答案是时间复杂度：O(log(n))，space复杂度O(log(log(n)))。

我的工作：
首先我决定计算函数 g3 的时间复杂度，因为 f3 在循环中调用它。 i 的值在 k 次迭代后为 2^k，每当 2^k >= n 时它就会停止，这意味着 k=log(n)。所以现在我知道 g3 的时间复杂度是 log(n)。
转到循环内的 f3，i 的值为 2,4,16,256 或换句话说 2^(2^k) 并且每当 2^(2^k) >= n 时它就会停止，所以我们得到 k = log(log(n)).
现在为了计算 f3 的整个时间复杂度，我知道函数 f3 总共调用了 g3 log(log(n)) 次。所以时间复杂度应该是这样的：

[log(2^(2^0))+log(2^(2^1))+...+log(2^(2^(log(log(n)))]*log(n)

请注意，所有这些都乘以 log(n)，因为每个调用在 g3 中迭代 log(n) 次（或者至少我是这样理解的）。
现在我被困在这里，因为我觉得我走得太远并犯了一些错误，我无法计算出总时间复杂度，也看不到它是 O(log(n))，我非常感谢任何帮助或反馈。
在此先感谢大家！

Answer 1

在计算复杂度之前，您的推理是正确的。每个调用不会在 g3 中迭代 log(n) 次，而是在 k 次迭代中迭代 log(2^(2^k)) 次。

让我们对 f3 进行一次迭代 k。此迭代具有复杂性 log(2^(2^k)))。由于 k 从 1 到 N=floor(log(log(n)))，总复杂度是 k=1 到 N 的 log(2^(2^k)) 的总和。使用属性 log(a^b) = b*log(a)，这给我们的时间复杂度等于 2^k 从 1 到 N 的总和（去掉乘法常数），这给我们，再一次摆脱乘法常数，时间复杂度为 O(2^N)。由于N=log(log(n))，我们最终得到了2^(log(log(n)))的时间复杂度。由于 log 在这里指的是以 2 为底的对数，因此最终我们得到了 O(log(n)).

的复杂度

关于时间复杂度，您存储 O(log(log(n))) 乘以一个值，这给出了 O(log(log(n))) 的 space 复杂度。

查找此程序的时间和 space 复杂度

Finding time and space complexity of this program

python

time-complexity

space-complexity