حل تكرار

Question

أحاول حل العودية المعطاة، باستخدام شجرة الإصابة، T(n) = 3T(n/3) + n/lg n.

في المستوى الأول (n/3)/(log(n/3)) + (n/3)/(log(n/3)) + (n/3)/(log(n/3)) = n/(log(n/3)).

في المستوى الثاني، اتضح أن يكون n/(log(n/9)).

هل يمكنني تعميم المعادلة المذكورة أعلاه في شكل n.loglogn

هذا شك كبير لدي، أحتاج إلى نظرة ثاقبة على هذا.

ملاحظة: أي وظيفة يجب أن تكون Theta(n^k log^k (n)) في هذه الوظيفة يجب أن K> = 1. وفي هذه الحالة K هي -1 لذلك لا يأتي نظرية ماجستير في الصورة

Answer 1

صحيح أن نظرية سيد لا ينطبق.

t (n) = 3t (n / 3) + n / logn.

دع G (n) = t (n) / n.

ثم N.ز (ن) = 3(n / 3) * g (n / 3) + n / logn.

هكذا

g (n) = g (n / 3) + 1 / log n.

هذا يعطي g (n) = sum 1 / log n + 1 / log n / 3 + 1 / log n / 9 + ...

= Theta (مجموع 1 / logn + 1 / (logn -1) + 1 / (log n - 2) + ... = theta (جزء لا يتجزأ من 1 / x بين 1 و logn) = theta (سجل السجل N).

هكذا ر (ن) = نg (n) = theta (nسجل logn.)

لقد خمنت ذلك بشكل صحيح.

Answer 2

إذا كنت تستخدم شجرة لتصور السؤال، فسترى أن مجموع كل رتبة هو:

• الرتبة 0:

(وهو ما يساوي n / log (n)) - المرتبة 1:

وهكذا دواليك، مع مبلغ عام n/log(n/(3^i)) لكل رتبة، أنا الرتبة الحالية. لذلك، كل ذلك نحصل على:

إذا فتحنا المعادلة نحصل عليه:

(بدءا من النهاية والذهاب إلى الوراء .. أولا عندما أكون = سجل (Base3) N ثم العودة)

منذ قاعدة السجل لا يهم في Theta، نحصل على:

الذي:

وهو (في سيغما):

وهي سلسلة متوازنة، تساوي:

وبما أن LN سجل مع قاعدة من E، ولا تهم قواعد السجل في Theta، فنحن نحصل أخيرا على:

وهو ما يساوي:

لذلك، إنه Theta (تسجيل الدخول N).