lua中的运行时间

首先，z=z + 1 该操作执行的次数等于函数结束时 z-1 的值。因此，如果我们可以对 f(n) 进行分析，那么 f 函数的复杂度将为 O(f(n))。让我们试着这样做。

其次，我们简化函数。以下循环

            for c=1,z do
                z=z+1
            end

等同于 z=z*2。接下来，以下循环

        for b=1,z do
            z=z*2
        end

等同于 z=z*(2^z)。现在我们可以等效地将整个函数重写成以下伪代码：

function f(n)
    local z=1
    for a=1,n do
        z=z*(2^z)
    end
    return z
end

现在我们可以递归地表示 f(n)：

f(n+1) = f(n) * 2^f(n)
       = 2^(f(1)) * 2^(f(2)) * ... * 2^(f(n))
       = 2^(f(1) + f(2) + ... f(n))

最后，让我们近似计算 f(n)：

f(n)   = 2^(f(1) + f(2) + ... f(n-1))
       ≥ 2^f(n-1)
       ≥ 2^(2^f(n-2))
       ≥ 2^^n

其中 a^^b = a^a^a^a^a...^a // a 在 b 次（这是 Knuth 的上箭头符号表示幂的运算符）。

我猜对于任何正常量 c>0，当 n 足够大时，以下不等式成立：2^^n > c * 2^(2^(2^(2^(2^(2^n)))))，因此问题的正确答案是 "其他都不是"。但是，我可能是错的。

您可以在 Computer Science StackExchange 上问问，对于 f(n)=2^(f(1) + f(2) + ... f(n-1))，O(f(n)) 是什么。