分治算法 - 时间复杂度

Question

有人可以帮忙解释下这个算法的时间复杂度吗？为什么它是O(n^2)？逐步解释会更有帮助，谢谢！

function divide(x,y)
    Input: Two n-bit integers x and y, where y >= 1
    Output: The quotient and remainder of x divided by y

    if x = 0:
        return (q,r) = (0,0)

    (q,r) = divide(x/2, y)
    q = 2q
    r = 2r

    if x is odd:
        r = r + 1

    if r >= y:
        r = r - y
        q = q + 1

    return (q,r)

- KP65

---

你能给你的代码添加“代码格式化”吗？现在它很难阅读。 - Skurmedel

需要澄清的是，算术运算是针对基本数据类型（例如 int）还是它们的数组（例如一个由 int 组成的 BigInt 数组）进行的？ - paxdiablo

不，这是一道过去的考题，我正在复习即将到来的考试。我有答案，但是我不理解：在算法的每次调用中，我们会失去一位。因此，会有n+1次调用。每次调用最多涉及2次乘以2（左移），两次加1和一次减去y的操作，它们都是O(n)。因此，总复杂度为O(n2)。 - KP65

@keval 移位、加法和减法通常被认为是O(1)，而不是O(n)。即使n非常大，你理论上也可以拥有一台能够在恒定时间内执行每个操作的机器。 - splicer

Answer 1

由于递归，divide（）将被调用多达n次。

假设对n位整数进行简单算术运算需要O（n）的时间。（在我所知道的所有大整数实现中都是如此--例如，在Python中，将1添加到大整数会复制整个整数。）

那么我们有一个有限数量的O（n）操作在最多n次内发生。这需要O（n^n）的时间。

def divide(x, y):
    assert y >= 1
    if x == 0:
        return 0, 0
    q, r = divide(x // 2, y)
    q *= 2
    r *= 2
    if x & 1:
        r += 1
    if r >= y:
        r -= y
        q += 1
    return q, r

- Jason Orendorff

---

我认为你把n搞混了。对单个n位整数进行算术运算的时间复杂度将是O(1)，而不是O(n)，因为我相信这里谈到的n是传递给函数的x的值。divide()永远不会被调用n次。传入1024将导致divide()仅被调用10次。 - paxdiablo

但是，Pax，您的帖子中说x和y是“两个n位整数”。 - Jason Orendorff

O(N) 中的 N 是 x 的值或位数 n 的数量，不能同时存在。我认为问题是针对单个整数单位（int），而不是一般数组（int[]），这使得 bigO 取决于两个输入变量。需要请问者澄清。 - paxdiablo

更正：原帖由keval发布，而非Pax。 - Jason Orendorff

我想你的意思是 n^2 而不是 n^n。 - keyser

Answer 2

最坏情况是x中的每个位都是1（例如0xffff），时间复杂度为O(n)。诀窍在于将递归转换为迭代。

- splicer

---

@splicer，我认为最坏的情况是当最高位为1时，而不一定是所有位。但是，现在我们已经确定n是位数，而不是x的值，因此O(n)才是正确的答案，尽管问题有误。加1并删除我的答案，该答案假设n是x的值而不是位数。 - paxdiablo

@Pax - 是的，你说得对：最坏情况就是当 MSB 被设置时。 - splicer