با سلام:
من یه چند تا سوال در قالب یه مو ضو ع مطر ح می کنم:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
تو این بخش مسعود عزیز و سایر دو ستان یه سری نکات گذاشتند. سوال من اینه اگه رابطه بازگشتی به این شکل باشه چه جوری باید حل کرد:
کد:
t(n)=t(n-1)+1/nیه مطلب دیگه هم در باره درخت بازگشت ممکنه تو این تا پیک درباراش بحث کنیم:
ببنید اگه
کد:
t(n)=t(n/2)+n^2اگه بخواهیم درخت بازگشت رو رسم کنیم و سپس بخواهیم مجموع نود‌ها هر سطح را باهم جمع کرده و در حالت کلی سیگما رو محاسبه کنیم این سری حا صل میشه ؟
کد:
n^2+1/2n^2+1/4n^2+.................+1/n(n^2)اما رابطه دیگه ای قرار داده شده .
کد:
t(n)=t(n/3)+t(2n/3)+nکد:
t(n)=t(n/2)+t(n/4)+t(n/8)+n(۰۸ بهمن ۱۳۸۹ ۰۳:۱۳ ب.ظ)لهمشد نوشته شده توسط:اگه درخت بازگشتیش رو بکشید مجموع سطوح این طوری میشه: [tex]\frac{1}{n} \frac{1}{n-1} ... \frac{1}{2} 1 = \log n[/tex]تو نکا تی که مسعود عزیز اشاره کرده این تابع از مرتبه تتا n هستش ولی تو کتاب اقای یوسفی گفته شده از مرتبه logn کلا اینجور توابع بازگشتی رو چطور باید حل کرد .کد:
t(n)=t(n-1)+1/n
(۰۸ بهمن ۱۳۸۹ ۰۳:۱۳ ب.ظ)لهمشد نوشته شده توسط: یه مطلب دیگه هم در باره درخت بازگشت ممکنه تو این تا پیک درباراش بحث کنیم:
ببنید اگهباشه برای حل ما میتونیم از قضییه اصلی استفاده کنیم . ولی می خوام از درخت بازگشت بررسی کنیم:کد:
t(n)=t(n/2)+n^2
اگه بخواهیم درخت بازگشت رو رسم کنیم و سپس بخواهیم مجموع نود‌ها هر سطح را باهم جمع کرده و در حالت کلی سیگما رو محاسبه کنیم این سری حا صل میشه ؟
و بعد چون تصا عدی کم داره میشه بنا براین از مرتبه تتا n^2 هستش .کد:
n^2+1/2n^2+1/4n^2+.................+1/n(n^2)
اما رابطه دیگه ای قرار داده شده .سوال من اینه اگه تو این رابطه با استفاده از درخت بازگشت بخواهیم بررسی کنیم چجوری باید حل بشهکد:
t(n)=t(n/3)+t(2n/3)+n
اگه دقت کنید میبینید که مجموع هر سطح n هست و طول طولانی ترین مسیر از ریشه به برگ [tex]\log_{\frac{3}{2}}n[/tex] هست پس مرتبه‌ی این رابطه‌ی بازگشتی [tex]n \log n[/tex] هست.
اون یکی هم شبیه همینه! فقط باید جمع هر سطح و ارتفاع درخت رو بتونید درست حساب کنید! همین!
فکر کنم اینا رو خودتونم می دونستید! به نظرم اگه سوالاتتون رو جزئی‌تر مطرح کنید و بگید که دقیقاً مشکلتون با چی هست، خیلی راحت‌تر و سریع‌تر بشه به سوالاتون جواب داد.
با سلام:
ممنون از همه دوستان که تو فهم مطالب کمک میکنند ممکنه رو این ۲ رابطه بازگشتی بحث کنید و بگید چطوری حل میشن ؟
واسه اولی درخت رسم کن. از ۲ فاکتور بگیر و لگاریتم‌ها رو جمع بزن . در پایان می شه ۲ ضربدر nlogn که می شه از مرتبه nlogn
دومی رو هم الان فکر می کنم اگر به ذهنم رسید راهش می گم. احتمالا تغییر متغیر می خواد
با سلام:
ممکنه بفرمایید ایندو رابطه چجوری حل میشن البته من خودم حل کردم من راه حل خودم رو می گم بعد اگه از دوستان کسی نظری داشتند بگن ممنون
تو اولی من مرتبه اش رو اوردم رادیکال n و تو دومیش از n/2 نسبت به رادیکال n میشه صر فنظر کرد البته در حد یه ایدهاست چون رشد رادیکال n از رشد n/2 بیشتر و طبق قضا یای چند جمله ای‌ها می تونیم از اونهایی که رشد کمتر دارند صر فنظر کنیم باز هم می گم اینها تحلیل خودمه اگه ایراد داره بفر مایید . در ضمن ازتون تشکر میکنم
اولی که از Master به راحتی حل می شه.
می شه [tex]\sqrt{n}*\log n[/tex]
دومی هم بعید می دونم که درست باشه گفته شما
چون نمی شه از چیز به این مهمی صرفنظر کرد
واسه دومی:
من یه جایی خوندم که رادیکال n خیلی کوچکتر از n/2 هستش. پس میتونیم ازش صرفه نظر کنیم و با استفاده از مستر حلش کنیم. که جواب این سوال به نظر من میشه [tex]\theta (n)[/tex]
سپید جان تغیر متغیرش رو فقط بگید کافیه. بگید که متغیر رو به چی باید تغییر بدیم؟
سلام:
رادیکال n کوچک تره ؟؟
نه کی گفته رادیکال n از مرتبه نمایی هستش و توابع نمایی رشدشون از توابع خطی بیشترها؟؟
نزن این حرفو برادر لهمشد عزیز: دی
رادیکال ۱۰۰۰ بزرگ تره یا خود ۱۰۰۰؟
معلومه که n مرتبه اش بیشتره از رادیکال n
من جزوه سید جوادی رو نخوندم فقط یه قسمتشو دیدم وقتی [tex]\sqrt{n}[/tex] داشتیم
از تغییر متغیر [tex]n=2^{2^{k}}[/tex] استفاده کرده بود خیلی جالب بود.
جزوش ۲۷ mb بود که به جای دانلود open کرده بودم
دیگه حوصله نداشتم دوباره دانلود کنم به دوستان توصیه میکنم قسمت مرتبه زمانی اش رو بخونید واسه دانلود هم به این لینک مراجعه کنید: مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
(۱۴ بهمن ۱۳۸۹ ۰۲:۰۲ ق.ظ)bijibuji نوشته شده توسط: نزن این حرفو برادر لهمشد عزیز: دیدرسته من اشتباه کردم نمی دونم چرا این چند وقت حواسم پرته عذر می خوام از اینکه مطلب اشتباهی رو مطرح کردم
رادیکال ۱۰۰۰ بزرگ تره یا خود ۱۰۰۰؟
معلومه که n مرتبه اش بیشتره از رادیکال n
t(n) = t(n-2)+2lg\left( n \right )///// t(n-2)=t(n-4)+2lg(n-2)////////
t(n-4)=t(n-6)+2lg(n-4)////////.......
.
.
.
t(2)=t(0)+2lg(2)============> t(n)=2lg(2)+2lg(4)+2lg(6)+...+2lg(n-2)+2lg(n)=2[lg(2*4*6*...* n-2 *n)]
=۲\left [ lg\left( 2^{\frac{n}{2}}*\left( \frac{n}{2} \right )! \right )\right ]=2\left [ lg2^{\frac{n}{2}} + lg\left( \frac{n}{2} \right )! \right ]=2\left [ \frac{n}{2}lg2 + lg\left( \frac{n}{2} \right )!\right ]=...=n+2lg\left( \frac{n}{2} \right )!= O\left( lg\left( \frac{n}{2} \right )! \right )=theta \left( nlgn \right )
[tex]t(n) = t(n-2) 2lg\left( n \right )/// t(n-2)=t(n-4) 2lg(n-2)/// t(n-4)=t(n-6) 2lg(n-4)///....... . . . t(2)=t(0) 2lg(2)=======> t(n)=2lg(2) 2lg(4) 2lg(6) ... 2lg(n-2) 2lg(n)=2[lg(2*4*6*...* n-2 *n)] =2\left [ lg\left( 2^{\frac{n}{2}}*\left( \frac{n}{2} \right )! \right )\right ]=2\left [ lg2^{\frac{n}{2}} lg\left( \frac{n}{2} \right )! \right ]=2\left [ \frac{n}{2}lg2 lg\left( \frac{n}{2} \right )!\right ]=...=n 2lg\left( \frac{n}{2} \right )!= O\left( lg\left( \frac{n}{2} \right )! \right )=theta \left( nlgn \right )[/tex]
روش بعدی روش درخت بازگشتی و یکی هم تغییر متغیر که یکی یکی توضیح میدم.