Diviser algorithme - temps complexité

Question

Quelqu'un peut-il aider à la complexité temporelle de cet algorithme, et pourquoi il est O (n^2). Une explication étape par étape serait utile, merci!

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

En raison de la récursivité, divide() est appelée jusqu'à n fois.

Supposons que des opérations arithmétiques simples sur des nombres entiers de n bits prend O (n). (Cela est vrai dans toutes les grandes implémentations d'entiers que je connais - en Python, par exemple, ajouter 1 à un grand entier copie le tout.)

Puis nous avons un nombre fini d'opérations O (n) jusqu'à n fois. Cela prend O (n^n) heure.

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

Le pire des cas, où chaque bit dans x est égal à 1 (par exemple 0xffff), est O (n). L'astuce consiste à convertir la récursion en une itération.