علاقة تكرار بناء على رمز الزائفة (تعقيد الوقت)

Question

النظر في مشكلة تفرد العنصر، حيث نحصل على مجموعة، وأنا، أنا + 1،. وبعد وبعد ، ي، من المؤشرات للحصول على صفيف، أ، ونريد تحديد ما إذا كانت عناصر هذا النطاق، A [i]، a [i + 1]،. وبعد وبعد ، A [J]، كلها فريدة من نوعها، أي أنه لا يوجد عنصر متكرر في هذه المجموعة من إدخالات الصفيف. النظر في الخوارزمية التالية (Inef Fi Cient).

giveacodicetagpre.

دع n تدل على عدد الإدخالات قيد النظر، وهذا هو، دع n= نهاية - البدء + 1. ما هو الجزء العلوي العلوي ملزمة في وقت التشغيل الزائد من شظية الكود هذا ل كبير n؟ تقديم تفسير موجز ودقيق. (تفقد علامات إذا كنت لا تفسر.) لبدء شرحك، قد تقول عدد المكالمات العودية ستجعل الخوارزمية قبل إنهاءها وتحليل عدد العمليات لكل عملية استدعاء لهذه الخوارزمية. بدلا من ذلك، يمكنك توفير تكرار تميز وقت التشغيل في هذه الخوارزمية، ثم حلها باستخدام تقنية استبدال التكرار؟

هذا السؤال هو من امتحان الممارسة العينة لفئة الخوارزميات هذه هي إجابتي الحالية يمكن أن تساعد في التحقق من ذلك إذا كنت على المسار الصحيح

الإجابة:

معادلة التكرار:

t (n)= 1 إذا n= 1، T (n)= 2T (N-1) إذا كان N> 1

بعد حل الاستبدال التكراري حصلت على

2 ^ k * t (n-k) وحل هذا إلى o (2 ^ (n-1)) وأبسطها O (2 ^ n)

Answer 1

يجب أن تكون علاقتك التكرار الخاصة بك T (n)= 2T (N-1) + O (1) مع T (1)= O (1).ومع ذلك، هذا لا يغير الزفاف، فإن الحل لا يزال ر (ن)= O (2 ^ n).لمعرفة ذلك، يمكنك توسيع علاقة تكرار الحصول على T (N)= O (1) + 2 (O (1) + 2 (O (1) + ...) لذلك لديك T (N)= O (1) * (1 + 2 + 4= ... + 2 ^ n)= O (1) * (2 ^ (n + 1) - 1)= O (2 ^ n).