سلام.
این سوال رو میشه با تکرار یا جایگذاری هم حل کرد، که بنظرم هم ساده هست.
روش به این صورت هست:

[tex]T(n) = T(n-2) 2Log(n)[/tex]
[tex]T(n) = T(n-4) 2Log(n-2) 2Log(n)[/tex]
[tex]T(n) = T(n-6) 2Log(n-4) 2Log(n-2) 2Log(n)[/tex]
[tex]T(n) = T(n-8) 2Log(n-6) 2Log(n-4) 2Log(n-2) 2Log(n)[/tex]
...
به همین صورت ادامه میدیم ، بصورت زیر مرتب میشه و از ۲ فاکتور میگیریم:

[tex]2\left [ Log(n) Log(n-2) Log(n-4) Log(n-6) Log(n-8) ... \right ][/tex]

نکته : لگاریتم خاصیتی داره به این صورت [tex]Log_{a} xy = Log_{a}x Log_{a}y[/tex] این یعنی که میشه بصورت زیر نوشت:

[tex]2Log\left [ n \times (n-2)\times (n-4)\times(n-6)\times(n-8)\times ... \right ][/tex]

باید راهی پیدا کنیم که لگاریتم رو بصورت منظمی در بیاریم، بصورتی که بشه با همون رابطه اصلی برابری کرد، اما چیزهایی رو بتونیم بهش اضافه یا کم کنیم:

[tex]2\left [Log\, \, \frac{ n \times (n-1)\times (n-2)\times(n-3)\times(n-4)\times (n-5)\times ...}{(n-1)\times(n-3)\times(n-5)\times ...} \right ][/tex]

همونطور که میبینید از تو قاعده ابتدایی طوری عمل کردیم که بشه بصورت فاکتوریل قضیه رو حل کرد، توچه کنید که تو صورت و مخرج عناصر اضافی باهم خواهند رفت و با قضیه بالایی برابر خواهد ماند:

نکته: لگاریتم خاصیتی داره به این صورت [tex]Log_{a}\frac{x}{y} = Log_{a}x - Log_{a}y[/tex] یعنی میشه بصورت زیر نوشت:

[tex]2\left [ Logn! \, \, -\, \, Log(n-1)\times(n-3)\times(n-5)\times... \right ][/tex]

نکته : طبق خاصیت گفته شده در کتاب ها، [tex]Logn!=nLogn[/tex] است. پس در نتیجه از سطر بالایی میتوان نتیجه گرفت که :

[tex]T(n) = \Theta (nLogn)[/tex]

این سوال رو کتاب پارسه هم حل کرده اما با جزئیات کمتر.
اگر جایی مبهم بود بگید بیشتر توضیح میدم.

(۰۱ آبان ۱۳۹۲ ۱۱:۴۳ ب.ظ)azad_ahmadi نوشته شده توسط:  سلام.
این سوال رو میشه با تکرار یا جایگذاری هم حل کرد، که بنظرم هم ساده هست.
...

توضیحاتتون عالی و کامل بودن.متوجه شدم. تشکر