math - 使用 big-O 表示法计算 x^2 中的位数？

Question

如果 x 是一个 n 位整数。x ²的大小（以位为单位）是多少？

我认为答案是 O(n); 那是对的吗？我想它的方式是向自身添加一个数字，该次数意味着将有 n 次操作，因此 O(n)。我的理解正确吗？

Answer 1

假设 x 有 n 位。这意味着 x = Θ(2 ⁿ )。因此，x ² = Θ(2 ⁿ · 2 ⁿ ) = Θ(2 ²ⁿ )，所以这个数字现在的位数大约是以前的两倍。这意味着如果一开始有 n 位，现在大约有 2n = Θ(n) 位。

虽然您给出的 O(n) 答案是正确的，但您的推理是无效的。请注意，问题不是询问计算 x ²需要多长时间，而是询问它包含的位数。计算 x ²的时间是另一个问题。

希望这可以帮助！