سلام بچه ها
میشه یکی طریقه بدست آوردن T(N)=T(N-2)+2logN رو که برابر T(N)=Θ(nlogn) میشه
رو یه توضیح مختصر بده. توی کتاب clrs اینو از طریق استقرا حل کرده بود. میشه از یه روش دیگه رفت؟؟؟
سلام.
این سوال رو میشه با تکرار یا جایگذاری هم حل کرد، که بنظرم هم ساده هست.
روش به این صورت هست:
[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 نوشته شده توسط: سلام.توضیحاتتون عالی و کامل بودن.متوجه شدم. تشکر
این سوال رو میشه با تکرار یا جایگذاری هم حل کرد، که بنظرم هم ساده هست.
...
