runtime - 计算 y^(3^n) 的算法的运行时间

Question

给定算法，

 y := 3
 for i = 1,...,n:
    y := y * y * y
 return y

我想确定它的运行时间。我认为该算法只是计算 y^(3^n)。但这与运行时无关，对吧？我认为运行时间由 n 决定，它将是 O(n)。那是对的吗？

标签： runtime

Answer 1

假设乘法 ( x * x) 是O(1)，那么您的代码的复杂性是O(n)。y如果在您的代码中使用机器整数表示，这就是您将得到的结果。

但问题是，如果您使用机器整数，x * x它将溢出足够大。x在这种情况下，这意味着代码不会计算 的正确值，除非和y^(3^n)的值非常小。ny

要获得较大值的正确答案，您需要使用“大整数”（或任意精度）表示。对于这样的表示，不再x * x是一个O(1)操作。它实际上是O(log(x).log(x))...

如果您使用“大整数”表示，我将由您来估计整个计算的复杂性。