تقسيم الخوارزمية - تعقيد الوقت

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-Bit يأخذ O (n) الوقت. (هذا صحيح في جميع تطبيقات الأعداد الصحيحة الكبيرة التي أعرفها - في بيثون، على سبيل المثال، إضافة 1 إلى عدد صحيح كبير نسخ كل شيء.)

ثم لدينا عدد محدود من عمليات O (ن) التي تحدث حتى الآن مرات. هذا يأخذ 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). الحيلة هي تحويل العودية إلى التكرار.