با عرض سلام. از درخت های بازگشتی برای حل چه روابط بازگشتیی استفاده میشود؟نحوه رسم اون رو هم لطفا توضیح بدبد.باتشکر فراوان
(۲۲ آذر ۱۳۸۹ ۰۵:۱۰ ب.ظ)bijibuji نوشته شده توسط: سولتون رو آقای هادی یوسفی در کتاب طراحی الگوریتمش (نشر پوران پژوهش) با رسم شکل و کامل توضیح داده.
اگر این کتاب در دسترستون هست به فصل اول اش (تحلیل الگوریتمها و مرتبه زمانی) یه نگاهی بندازید.
بله میدونم.ولی من تو فصل بازگشتی کتاب آقای یوسفی تقریبا مشکل اصلیم همین مسئله رسم درخت بازگشتی بوده که نفهمیدم.لطفا این مثال رو با تحلیل برام توضیح بدین.تشکر.
tn=t n/3 +t 2n/3 + On
ارسال #۸ و#۱۰ رو ببینید
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
این هم رسم درخت
(فایل ضمیمه)
ببینید توی هر مرحله یه n تولید میشه و طبق توضیحی هم که توی اون ارسال دادم باید ببینیم کدوم شاخه طولانیتر هست.
(۲۳ آذر ۱۳۸۹ ۰۱:۲۳ ب.ظ)sos006 نوشته شده توسط:(22 آذر ۱۳۸۹ ۰۵:۱۰ ب.ظ)bijibuji نوشته شده توسط: سولتون رو آقای هادی یوسفی در کتاب طراحی الگوریتمش (نشر پوران پژوهش) با رسم شکل و کامل توضیح داده.
اگر این کتاب در دسترستون هست به فصل اول اش (تحلیل الگوریتمها و مرتبه زمانی) یه نگاهی بندازید.
بله میدونم.ولی من تو فصل بازگشتی کتاب آقای یوسفی تقریبا مشکل اصلیم همین مسئله رسم درخت بازگشتی بوده که نفهمیدم.لطفا این مثال رو با تحلیل برام توضیح بدین.تشکر.
tn=t n/3 +t 2n/3 + On
مفهوم رو گرفته باشید، خیلی براتون واضح می شه. منظورم مفهوم ایده بازگستی هستش.
شما یه تابعی داری به نام T که این مدت زمان محاسبه یک لگوریتم خاص رو نشون میده بر حسب n
این رو میای بر حسب دو مقدار کمتر محاسبه می کنی. اگر به مسائل تقسیم و غلبه نگاه کنیم بهتر درکش می کنیم. تابع Tبرای گره n بر حسب مقادیر همین تابع برای گره های n/3 و ۲n/3 محاسبه می شه و در انتها با هزینه n با هم ترکیب می شن.
پس واسه محاسبه باید کل گره های درخت بازگشتی رو مقادیرش رو جمع بزنیم.
حالا شما با هر تکنیکی که دلت می خواد و راحتی جمع بزن.
یا یه مدلی پیدا کن و به یک تصاعد هندسی یا حسابی برس
یا اگر مجموع هر سطح از گره های درخت مساوی بود این مقدار رو در ارتقاع درخت ضرب کن (که معمولا ارتفاع لگاریتمی هست) ....
خلاصه کلام اینکه به هر شیوه ای که بتونی مجموع مقادیر کل گره های درخت رو با هم جمع بزنی، مقدار T رو برای n محاسبه کردی
موفق باشی