2

我遇到了这个问题，我不知道如何解决：

假设 A(.) 是一个将二进制数作为输入的子程序，并且需要线性时间（即 O(n)，其中 n 是数字的长度（以位为单位））。考虑以下一段代码，它以 n 位数 x 开头。

while x>1:
  call A(x)
  x=x-1

假设对一个 n 位数进行减法运算需要 O(n) 时间。

(a) 内循环迭代多少次（作为 n 的函数）？以大 O 形式留下您的答案。

(b) big-O 形式的总运行时间（作为 n 的函数）是多少？

我的猜测是 (a) 是 O(n^2) 而 (b) 是 O(n^3)。这个对吗？我正在考虑的方式是，循环必须在每次循环时计算两个步骤，并且每次从 n 位中减去 1 直到 x 达到 0，它都会循环 x 次。对于 b 部分，因为 A(.)需要时间 O(n) 我们将其乘以执行循环所需的时间，然后我们就得到了所有运行时间。我的分析正确吗？

4

1 回答 1

7

这里可能有帮助的是写 x = 2 n，因为如果 x 有 n 位，它的值是 O(2 n )。因此，循环将运行 O(2 n ) 次。

循环的每次迭代都做 O(n) 工作，给出 O(n · 2 n )工作的上限。这个界限最终变得很紧。请注意，对于循环的前 x/2 次迭代，x 的值仍需要 n 位。因此，作为完成工作的下限，我们得到 x/2 = 2 n-1次迭代，每次做 n 个工作，总共有 Ω(n · 2 n ) 个工作。因此，所做的工作是 Θ(n · 2 n )。

希望这可以帮助！

于 2013-10-25T07:23:33.343 回答