除法算法-时间复杂度

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)

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

Answer 2

最坏的情况是 O(n)，其中 x 中的每一位都是 1（例如 0xffff）。 诀窍是将递归转换为迭代。