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

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

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

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

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

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

$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 ]$

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

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

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

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

$T(n) = \Theta (nLogn)$

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

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

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