Алгоритм разделения - сложность времени

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

В худшем случае, где каждый бит х равен 1 (например, 0xFFFF), представляет собой О (п). Трюк состоит в том, чтобы преобразовать рекурсию в итерацию.