زمان کنونی: ۲۴ آبان ۱۴۰۳, ۰۸:۴۸ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

سوال از الگوریتم بازگشتی

ارسال:
  

g_monireh پرسیده:

سوال از الگوریتم بازگشتی

سلام بچه ها
میشه یکی طریقه بدست آوردن T(N)=T(N-2)+2logN رو که برابر T(N)=Θ(nlogn) میشه
رو یه توضیح مختصر بده. توی کتاب clrs اینو از طریق استقرا حل کرده بود. میشه از یه روش دیگه رفت؟؟؟
نقل قول این ارسال در یک پاسخ

۱
ارسال:
  

azad_ahmadi پاسخ داده:

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]

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

ارسال:
  

g_monireh پاسخ داده:

RE: سوال از الگوریتم بازگشتی

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

نقل قول طولانی ممنوع Smile

یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  الگوریتم نوبت گردشی 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?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close