۱
subtitle
ارسال: #۱
  
سوال از الگوریتم بازگشتی
سلام بچه ها
میشه یکی طریقه بدست آوردن T(N)=T(N-2)+2logN رو که برابر T(N)=Θ(nlogn) میشه
رو یه توضیح مختصر بده. توی کتاب clrs اینو از طریق استقرا حل کرده بود. میشه از یه روش دیگه رفت؟؟؟
میشه یکی طریقه بدست آوردن T(N)=T(N-2)+2logN رو که برابر T(N)=Θ(nlogn) میشه
رو یه توضیح مختصر بده. توی کتاب clrs اینو از طریق استقرا حل کرده بود. میشه از یه روش دیگه رفت؟؟؟
۱
ارسال: #۲
  
RE: سوال از الگوریتم بازگشتی
سلام.
این سوال رو میشه با تکرار یا جایگذاری هم حل کرد، که بنظرم هم ساده هست.
روش به این صورت هست:
[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]
این سوال رو کتاب پارسه هم حل کرده اما با جزئیات کمتر.
اگر جایی مبهم بود بگید بیشتر توضیح میدم.
این سوال رو میشه با تکرار یا جایگذاری هم حل کرد، که بنظرم هم ساده هست.
روش به این صورت هست:
[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]
این سوال رو کتاب پارسه هم حل کرده اما با جزئیات کمتر.
اگر جایی مبهم بود بگید بیشتر توضیح میدم.
ارسال: #۳
  
RE: سوال از الگوریتم بازگشتی
(۰۱ آبان ۱۳۹۲ ۱۱:۴۳ ب.ظ)azad_ahmadi نوشته شده توسط: سلام.توضیحاتتون عالی و کامل بودن.متوجه شدم. تشکر
این سوال رو میشه با تکرار یا جایگذاری هم حل کرد، که بنظرم هم ساده هست.
...
Masoud05، در تاریخ ۰۴ آبان ۱۳۹۲ ۰۲:۵۰ ب.ظ برای این مطلب یک پانوشت گذاشته است:
نقل قول طولانی ممنوع
موضوعهای مرتبط با این موضوع... |
|||||
موضوع: | نویسنده | پاسخ: | بازدید: | آخرین ارسال | |
الگوریتم نوبت گردشی | mhasa | ۴ | ۳,۷۰۰ |
۱۴ بهمن ۱۳۹۵ ۱۰:۵۴ ب.ظ آخرین ارسال: mhasa |
|
نحوه ورود فرایند ها در الگوریتم RR | abji22 | ۱۳ | ۵,۳۲۸ |
۲۴ دى ۱۳۹۳ ۱۲:۱۴ ق.ظ آخرین ارسال: abji22 |
|
۱۷۳ نرم، الگوریتم و محاسبات | El@he | ۲ | ۲,۳۱۸ |
۱۳ مهر ۱۳۹۳ ۰۶:۱۴ ب.ظ آخرین ارسال: H3NGAM3H |
|
سوال از رابطه بازگشتی | amir2930 | ۱ | ۱,۲۸۸ |
۰۱ شهریور ۱۳۹۳ ۱۰:۵۱ ق.ظ آخرین ارسال: MShariati |
|
الگوریتمA*الگوریتم جستجو نیست؟ | abji22 | ۶ | ۴,۹۴۷ |
۱۰ بهمن ۱۳۹۲ ۱۲:۱۴ ق.ظ آخرین ارسال: H3NGAM3H |
|
مرتبه زمانی یک رابطه بازگشتی | amin222 | ۷ | ۵,۶۸۹ |
۳۰ دى ۱۳۹۲ ۰۳:۵۰ ب.ظ آخرین ارسال: misagh01 |
|
سوال الگوریتم sort sort | amir2930 | ۱ | ۱,۳۷۶ |
۱۸ آذر ۱۳۹۲ ۱۱:۴۰ ق.ظ آخرین ارسال: MShariati |
|
مرتبه زمانی یک تابع بازگشتی | amin222 | ۱۴ | ۷,۱۶۶ |
۰۹ آذر ۱۳۹۲ ۰۱:۰۵ ق.ظ آخرین ارسال: ریحان |
|
مشکل در الگوریتم SMA* | g_monireh | ۵ | ۵,۳۳۹ |
۲۹ مهر ۱۳۹۲ ۰۸:۰۶ ب.ظ آخرین ارسال: tarane1992 |
|
کتاب منبع برای درس تجزیه و تحلیل الگوریتم ها در آزمون دکترا | science67 | ۱۲ | ۱۴,۲۶۸ |
۰۳ مهر ۱۳۹۲ ۱۰:۳۱ ب.ظ آخرین ارسال: remis123 |
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close