除法算法 - 时间复杂度

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

由于递归，除法（）被调用最多n次。

假设在n位整数简单的算术需要O（n）的时间。 （这是在所有的大整数实现我知道真 - 在Python，例如，将1加到一个大整数拷贝整个事情）

然后，我们有发生多达n倍为O（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

在最坏的情况下，其中，在X的每一位是1（例如0xFFFF）时，为O（n）。诀窍是递归转换成迭代。