(۲۸ اسفند ۱۳۹۷ ۱۰:۴۰ ق.ظ)npour نوشته شده توسط:  

(27 اسفند ۱۳۹۷ ۱۱:۵۵ ب.ظ)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 هست. چون میدونیم که ثوابت و پایه لگاریتم تاثیری در مرتبه ندارند. ولی برای اینکه دقیق بدونید داره چه اتفاقی میفته و برای حل سوالات دیگه، خوبه که بدونید این جزئیات رو.

(۲۸ اسفند ۱۳۹۷ ۱۱:۴۵ ق.ظ)Sanazzz نوشته شده توسط:  

(28 اسفند ۱۳۹۷ ۱۰:۴۰ ق.ظ)npour نوشته شده توسط:  

(27 اسفند ۱۳۹۷ ۱۱:۵۵ ب.ظ)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 هست. چون میدونیم که ثوابت و پایه لگاریتم تاثیری در مرتبه ندارند. ولی برای اینکه دقیق بدونید داره چه اتفاقی میفته و برای حل سوالات دیگه، خوبه که بدونید این جزئیات رو.

بی نهایتتتت تشکر
خیلی خیلی خیلی خیلییییییی ممنونمممم
تشکرااااااااات ویژههههههههههه
واقعا ممنون

(۲۶ اسفند ۱۳۹۷ ۰۶:۵۲ ب.ظ)saho نوشته شده توسط:  

(26 اسفند ۱۳۹۷ ۰۶:۲۸ ب.ظ)Sanazzz نوشته شده توسط:  

(26 اسفند ۱۳۹۷ ۰۶:۲۷ ب.ظ)saho نوشته شده توسط:  

(26 اسفند ۱۳۹۷ ۰۵:۳۸ ب.ظ)Sanazzz نوشته شده توسط:  

(26 اسفند ۱۳۹۷ ۰۵:۲۵ ب.ظ)saho نوشته شده توسط:  نه جواب قطعا گزینه ۲ هستش.هرکس بود باقضیه اشنانبوده.
درهت هم بکشین همین میشه.
هر سطح n + 1/logn
که اینlog ها اینقدر زیاد میشه که در برابر n چیزی نخواهد بود

ممنون از این که جواب دادین
خودش راه حل رو این نوشته

راستش من با درخت واسه رابطه بازگشتی و حل کردن این مدلی خیلی مشکل دارم میشه لطفاا یه مقدار بیشتر توضیح بدین

اخه اصلا نیاز به درخت نیست.اما درخت هم شما تقسیم کنیم و تملم سطوحو باهم جمع کنین.
ببخشید این جوابو کی گذاشته؟ کتابش معتبره؟!!سوال کنکوره؟

آزمون مدرسان
ولی من جوابشو اصلا متوجه نمیشم

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.


ظاهرا مسئله ی معروفیه!!! همون میشه.اما اصلا نفهمیدم

(۲۶ اسفند ۱۳۹۷ ۰۵:۲۵ ب.ظ)saho نوشته شده توسط:  

(26 اسفند ۱۳۹۷ ۰۲:۴۱ ب.ظ)Sanazzz نوشته شده توسط:  سلام
جواب این سوال میشه گزینه ۳
ولی اگر از قضیه بریم مگه نمیشه گزینه ۲
میشه لطفا کمککککککک
خواهشا
ممنون میشم

نه جواب قطعا گزینه ۲ هستش.هرکس بود باقضیه اشنانبوده.
درهت هم بکشین همین میشه.
هر سطح n + 1/logn
که اینlog ها اینقدر زیاد میشه که در برابر n چیزی نخواهد بود