(۲۷ اسفند ۱۳۹۷ ۱۱:۵۵ ب.ظ)Sanazzz نوشته شده توسط: (27 اسفند ۱۳۹۷ ۰۹:۲۴ ب.ظ)npour نوشته شده توسط: (27 اسفند ۱۳۹۷ ۰۵:۳۸ ب.ظ)Sanazzz نوشته شده توسط: من یه درخت بازگشت براش کشیدم ولی نمیدونم واسه سیگما باید i از چند شروع بشه
اون قسمتی هم که دورش ابر کشیدم از سایتی که گذاشته بودین نوشتم
باید جوابش log به توان دو بشه ولی من حساب میکنم میشه log به توان سه
میشه لطفا یه نگاهی کنین
ممنون میشم
سلام در تلاش بودم فایل عکس پیوست کنم
(۲۷ اسفند ۱۳۹۷ ۰۵:۳۸ ب.ظ)Sanazzz نوشته شده توسط: من یه درخت بازگشت براش کشیدم ولی نمیدونم واسه سیگما باید i از چند شروع بشه
اون قسمتی هم که دورش ابر کشیدم از سایتی که گذاشته بودین نوشتم
باید جوابش log به توان دو بشه ولی من حساب میکنم میشه log به توان سه
میشه لطفا یه نگاهی کنین
ممنون میشم
هزینه به ۱ نمیرسه
بلکه فراخوانی بازگشتی به ۱ میرسه
یعنی
T(n/4^i)=T(1)
و ارتفاع درخت میشه لگاریتم n در مبنای ۴
اون قسمتی که دورش ابر کشیدید فکر میکنم یا باید اندیس سیگما رو k بگذارید یا متغیر k رو i بگذارید که میشه تعریف سری هارمونیک..
خیلی خیلی خیلی خیلی خیلی خیلییییییییییی مممنونممممممممم
بالاخره درست شد؟؟؟
واقعا تشکرات ویژه
من انقدر بخاطر این درخت های بازگشتی اعصابم خرد بود
واقعا ممنون
دعا میکنم هر چی میخواین خدا بهتون بده
تشکراااات ویژهههههههههه
سلام. چند تا اشتباه خیلی ریز وجود داره که میگم حضورتون.
اول اینکه توی اون ابر که کشیدید اگه دقت بفرمایید مخرج کسر نباید ۰ باشه..بنابراین از ۱ شروع کنید سیگمای ابر رو.
دوم اینکه توی سیگمای هزینه سطح بالا رو بر حسب n باید بنویسید. ( لگاریتم n در مبنای ۴ درسته . لگاریتم i در مبنای ۴ اشتباه هست.)
سوم اینکه طبق نوشته کتاب کرمن ( که مرجع اصلیمون هست) در درس ساختمان و الگوریتم هرجا نوشته شده باشه log شما در مبنای ۲ حسابش کنید. در واقع در این درس لگاریتم طبیعی مبنای ۲ هست و به این هم به خاطر درخت دودویی و محاسبات هست. پس قسمت دوم این رابطه که هستش n/log n رو شما باید هزینه (نه ارتفاع ) رو بدونید که لگاریتم در پایه ۲ هست.
چهارم اینکه باز طبق کرمن، در درختهای بازگشتی که پر هستند( مثل همین مثال) سطح آخر رو سوا حساب میکنه. یعنی در واقع برای سطح آخر میاد تعداد برگ ها رو در هزینه یک برگ ضرب میکنه و سیگما رو تا سطح یکی مانده به اخر مینویسه. اگه شما توی همین مثال به جای i بگذارید لگاریتم n در مبنای ۴ مخرج کسر میشه لگاریتم ۱ در مبنای ۴ یعنی صفر که اشتباه هست. بنابراین سیگما رو تا سطح یکی مونده به اخر بنویسید و هزینه سطح اخر( یعنی برگها) رو سوا حساب کنید و باهاش جمع کنید. ( میدونیم که حداکثر تعداد برگها در درخت k تایی برابر هست با k به توان ارتفاع درخت و چون اینجا درخت پر هست، تعداد برگها حداکثر هست. k=4 و ارتفاع هم لگاریتم n در مبنای ۴ هست. پس تعداد برگها میشه n و هزینه هر برگ هم عدد ثابت هست. پس هزینه میشه n ضرب در تتای ۱ که کلا میشه تتای n)
موارد ۳, ۴ که گفتم خدمتتون توی مرتبه این رابطه بازگشتی تاثیر نمیگذاره و مرتبه این رابطه از نظر مجانبی برابر تتای nloglogn هست. چون میدونیم که ثوابت و پایه لگاریتم تاثیری در مرتبه ندارند. ولی برای اینکه دقیق بدونید داره چه اتفاقی میفته و برای حل سوالات دیگه، خوبه که بدونید این جزئیات رو.