为什么这个算法是 O(n^2)

Question

function multiply(x, y)
  Input: Two n-bit integers x and y, where y ≥ 0 Output: Their product
  if y=0: return 0 
  z = multiply(x, ⌊y/2⌋) 
  if y is even:
    return 2z 
  else:
    return x + 2z

如我的问题所述，为什么这个函数是 O(n^2)？这是书上的解释，上面的例子属于：

It must terminate after n recursive calls, because at each call y is halved—that is, its number of bits is decreased by one. And each recursive call requires these operations: a division by 2 (right shift); a test for odd/even (looking up the last bit); a multiplication by 2 (left shift); and possibly one addition, a total of O(n) bit operations. The total time taken is thus O(n^2), just as before.

因为除以2和乘法的左移和右移，我认为它会大于O(n^2)..maybe n^3.

Answer 1

每个操作右移、测试、左移每个位需要固定的时间量，因此每次递归完成 O(n) 次。请记住 O(3n) 仍然是 O(n)。

由于整个函数使用左移递归地应用于每个位，因此前面的 O(n) 个步骤执行了 O(n) 次，使得总复杂度为 O(n^2)。

Answer 2

这是comp-sci教材还是VLSI教材？因为答案取决于操作 y==0、y/2、2z、x+2z 和 "y is even".

的复杂性

作为应用程序开发人员，我认为这些是恒定时间操作，所以它们都是 O(1)。乘法函数是 O(log(Y)) 或 O(N)，其中 N 是 Y 中的位数。同样的事情。因此，我得出结论，这整个函数是 O(N).

现在，计算机工程师可能会争辩说 y/2 需要移动 N 位，因此它是一个 O(N) 操作。可能有一些 CPU 是这样工作的。请允许我荒谬一会儿，并争辩说我可以为 y==0 创建一个需要 O(N^47) 的实现，因此这个函数是 O(N^48)。 :-)

实际上，任何现代的 N 位处理器都会并行地对 N 位数字进行位移，因此它们确实是 O(1)。也许在 8088 上情况并非如此，但对于任何现代设计来说都是如此。所以实际上我认为这是 O(N) 而不是 O(N^2)

为什么这个算法是 O(n^2)

Why this algorithm is O(n^2)

big-o