تالار گفتمان مانشت - مبحث اول : روابط بازگشتی ، نمادهای مجانبی و تحلیل الگوریتم ها (بازگشتی و غیر بازگشتی )

رابطه بازگشتی

Sun, 18 Sep 2016 18:08:30 +0000

سلام
حل این رابطه بازگشتی از چه مرتبه زمانی است؟
( با روش تغییر متغیر)
k<=2 T(k)=1
T(n)=n^1/2T(n^1/2)+n

یک رابطه بازگشتی

Tue, 09 Apr 2013 09:35:14 +0000

اگر حداکثر تعداد نواحی که با رسم n خط راست در صفحه به وجود می آید را با (R اندیس n) نشان دهیم یک رابطه بازگشتی برای (R اندیس n) پیدا کنید و آنرا حل نمایید.

این سوال کنکور دانشگاه دولتیه ممنون میشم کمکم کنید تا جوابش رو پیدا کنم

راهنمایی برای حل روابط بازگشتی

Sat, 22 Dec 2012 13:46:35 +0000

سلام به همه مانشتی های عزیز

چند وقتی میشه که دارم با این مسائل بازگشتی تو الگوریتم سر و کله میزنم ولی مطلب رو نمی گیرم.

مباحث اصلی مشکل ام:
۱- حل روابط بازگشتی
۲- علامت گذاری مجانبی(مرتبه ها)

منبع الانم هم پارسه هست.
دوستان چه پیشنهادی میدن؟
جزوه یا منبع خاصی رو پیشنهاد می کنند که این بحث رو روان و کامل توضیح داده باشه؟

پیشاپیش متشکرم.

بهترین جواب رابطه بازگشتی

Sat, 22 Sep 2012 13:39:02 +0000

[tex]G(0)=1,G(1)=2,G(2)=4, G(n)=G(n-1) 2G(n-2) G(n-3)[/tex]

برای[tex]n\geq 3[/tex] کدام گزینه زیر بهترین جواب این رابطه است؟

جواب::[tex]g(n)\leq 4^{n}[/tex]

گزینه دیگه:[tex]g(n)\leq 2^{n 1}[/tex]

اینکه چرا[tex]g(n)\leq 4^{n}[/tex] متوجه میشم اما [tex]g(n)\leq 2^{n 1}[/tex] این نمیشه ،رو نمیتونم ثابت کنم

زمان مصرفی رابطه بازگشتی

Sat, 22 Sep 2012 13:24:30 +0000

[tex]t(n)=t(2n/3) (logn)^{2}[/tex] زمان مصرفی الگوریتم؟اگه ممکنه یه حل دقیق بدین؟

جواب:[tex](logn)^{3}[/tex]

حل تابع بازگشتی

Sun, 16 Sep 2012 07:42:44 +0000

t(1)=0
t(n)=t(n-1)+2/n

دوستان اگه ممکننه حل دقیق بدین،یجا با جایگذاری حل کرده اما من متوجه نمیشم