كيفية حل التكرار.تي (ن).= تي(ن-1) + تي(ن/2) + ن؟

Question

أدرك أنه للحصول على وقت تشغيل باستخدام طريقة شجرة العودية، نحتاج إلى رسم شجرة والعثور على:

أ) عدد المستويات في الشجرة.

نظرًا لأن حجم الجانب الأيسر من الشجرة يتناقص بمقدار 1، فهو أطول مسار من الجذر.حجم المشكلة الفرعية في المستوى الأول هو n-i .إعداد n - i = 1 عندما يصل إلى حجم 1، نحصل على عدد المستويات، i = n - 1.

ب) التكلفة لكل عقدة في الشجرة : cn

ج) عدد العقد في المستوى الأول:هذا هو المكان الذي أنا عالقة.غير قادر على العثور على العقد في المستوى i نظرًا لأن الجانب الأيسر يتناقص بمقدار 1، والجانب الأيمن بمقدار النصف.وبطبيعة الحال، تكون الشجرة أكثر كثافة باتجاه الجانب الأيسر.لن يكون لكل عقدة طفلان.

إذا كان بإمكاني الحصول على إجابة ج، فيمكنني حساب T(n) = تكلفة المستوى 0 + تكلفة المستوى 1 + تكلفة المستوى 2 + ...تكلفة المستوى n-1.إذا كان y1 هو عدد العقد في المستوى 1، وy2 في المستوى 2، وما إلى ذلك...ثم
=> T(n) = cn + y1 * cn + y2 * cn + y3 * cn + ....yn-1 * cn للحصول على التكلفة الإجمالية.

هل يمكن لأي شخص أن يرشدني إلى النهج الذي أتبعه؟هل هذا صحيح ؟هل يمكنني أن أفترض أنه بالنسبة لـ n كبير بدرجة كافية، يمكننا تجاهل T(n/2) ثم المتابعة؟.

البحث على الإنترنت أربكني.المشكلة هي 4.4-5 من CLRS.

لطفا أنظر هنا

يقول هذا الحل T(n) = O(2^n) وT(n) = omega(n^2) ولا يشرح كيف.

انظر أيضا هنا

يقول هذا الحل T(n) = O(n^2).ولكن يتعارض مع الحل أعلاه

Answer 1

يترك $S(n) = T(n) - 2n - 2$.يمكنك التحقق من ذلك $S(n) = S(n-1) + S(n/2)$ (متجاهلاً حقيقة ذلك $ن/2$ ليس من الضروري أن يكون عددًا صحيحًا).وهذا يدل على أن المادة المضافة $ن$ المصطلح لا يحدث فرقا كبيرا.

لكبير $ن$, ، لدينا تقريبا $S(n) - S(n-1) \تقريبًا S'(n)$, وهكذا نحن قادرون على حل المعادلة التفاضلية$$يعتبر $f(n) = \exp ( frac{1}{2}\log_2^2 n)$.ثم$$ f'(n) = \exp (\tfrac{1}{2}\log_2^2 n) \cdot \frac{\ln n}{(\ln 4)n}, $$بينما$$وهذا يوحي بأنه، على أقل تقدير، $\ln S(n) = heta(\log^2 n)$.

من أين يأتي هذا؟يمكن ان يخطر لك $S(ن)$ (مع حالة أساسية مناسبة!) كعدد الطرق التي يمكن الانتقال منها $ن$ إلى الصفر من خلال تطبيق عمليتين:اطرح 1 واقسم على 2.سيحتوي هذا التسلسل "النموذجي" تقريبًا $\log_2n$ العديد من العمليات من النوع الثاني، من $\ثيتا(ن)$ العمليات في المجموع، مما يؤدي إلى تقدير تقريبي للغاية $\binom{ heta(n)}{\log_2 n}$, ، وهو أيضًا من الشكل $\exp heta(\log^2 n)$.

---

خذ في الاعتبار التعريف الدقيق التالي لـ $S(ن)$:الحالة الأساسية هي $S(0) = 1$, ، ولل $ن> 0$, $$هذا هو التسلسل A000123.نوث, تكرار خطي تقريبا, ، أظهرت أن$$ \log_4 S(n) \sim \log_4^2 n, $$أي أن نسبة المصطلحين تميل إلى 1 as $n \إلى \infty$.يحتوي إدخال OEIS على خطوط مقاربة أكثر دقة.

Answer 2

أنا لا أتفق مع التنويم المغناطيسي فيبوناتشي، لكنني لست متأكدًا بنسبة مائة بالمائة من إجابتي

هل ترى$ T(n)= T(n-1) +c*n = O(n ^2) $

$ T(n) = T(n/2) + c*n =O(n log n) $

ومع ذلك، لا تحصل على T(n) الخاص بك عن طريق الإضافة المباشرة.

إذا انتقلت إلى مستوى واحد في العودية (يمكنك رسم شجرة)

T(n) =T(n-2) +T((n-1)/2) +T(n/2-1)+ T(n/4) + [n + (n-1) + (n-1)/2 + (n/2-1) +n/4]

هذا لتظهر لك أنه ليس فقط $ يا (ن ^ 2) $

لا بد لي من إكماله، ولكني أشك في ذلك أيضًا $ O ((ن ^ 2) * سجل ن) $أو $ O((n^2) * n ^ {log n} ) = O(n^3) $

{يوجد مصطلح n(1+1/2+1/4+..1/n) يتحلل في خطوات السجل n، يجب أن أتحقق مرة أخرى}