🙏 کلید من برای سوالات داده الگوریتم مهندسی ارشد ۴۰۴
۵۶. گزینه سوم. طبق قضیه آکرا-بازی p=2 خواهد بود و به انتگرال
∫1/xlgx dx=lglgx
خواهید رسید که پاسخ سوال میشه
θ(x²lglgx)
۵۷. گزینه چهارم. مشابهش تو کلاس گفته بودم.
۵۸. گزینه اول. تعداد زیر دنباله‌ها دو به توان ان هستش. بدون افزایش هزینه زمانی میتوان تمام زیر دنباله‌های یک دنباله رو با همان مرتبه
2^n
تولید و بررسی کرد.
۵۹. گزینه چهار. همان مسئله کوله پشتی می‌باشد و اگر نسخه گریدی کوله پشتی غیر صفر یک و به ما تو اون نود خاص جواب بهتری بده باید از اینجا بک‌ترک بزنیم و جلو‌تر نریم.! پس این هیورستیک بهتره نسبت به مابقی گزینه‌ها.
۶۰. گزینه دوم. عینا تو کلاس گفته شده بود این و تمرین مرجع هم بود!!!!!!
۶۱. گزینه اول. اولی مرتبه ان میشه. گزینه دوم هر بار داره همه رو از نو محاسبه میکنه سوم و چهارم هم مشخصه مثل دومی عمل میکنه
۶۲. گزینه اول. تو بهینه محلی گیر میکنه و ممکنه جواب بهینه رو برای این مسئله خاص پیدا نکنه. مابقی گزینه‌ها رد میشن چون نسخه‌های خاص‌اش نیاز به حل دقیق نیست و میشه با همین حریصانه جواب بهینه رو بدست آورد.
اساسا این سوال کلی ابهام داره!!!! احتمال حذفش هست به نظرم. چون موارد دوم تا یکی به آخر هم غلط نیستن واقعیت.
۶۳. گزینه سوم. مشابهش تو کلاس بوده
۶۴. گزینه دوم. تو اسلایدهای کلاس بوده عینا
۶۵. گزینه سوم. هرم دوتایی مرتبه حذف درج و حذف مکس میاره روی لاگ‌ان و به کمک داده ساختار مرتب AVL که سایز هر زیر درخت ذخیره کردیم می‌تونیم میانه رو تو لاگ ان پیدا کنیم. با هرم دوتایی هم میانه به راحتی به دست میاد. تمرین MIT بوده.
۶۶. گزینه سوم. اثباتش https://mathcenter.oxford.emory.edu/site/cs171/quickSortAnalysis/#:~:text=Thus%2C%20on%20average%20the%20quick,data%20movement%20during%20the%20sort.
۶۷. گزینه دوم. سایر گزینه‌ها ظاهراً دقیقا به نود 3n/4 خواهند رسید.
۵۶. گزینه سوم. طبق قضیه آکرا-بازی p=2 خواهد بود و به انتگرال
∫1/xlgx dx=lglgx
خواهید رسید که پاسخ سوال میشه
θ(x²lglgx)
۵۷. گزینه چهارم. مشابهش تو کلاس گفته بودم.
۵۸. گزینه اول. تعداد زیر دنباله‌ها دو به توان ان هستش. بدون افزایش هزینه زمانی میتوان تمام زیر دنباله‌های یک دنباله رو با همان مرتبه
2^n
تولید و بررسی کرد.
۵۹. گزینه چهار. همان مسئله کوله پشتی می‌باشد و اگر نسخه گریدی کوله پشتی غیر صفر یک و به ما تو اون نود خاص جواب بهتری بده باید از اینجا بک‌ترک بزنیم و جلو‌تر نریم.! پس این هیورستیک بهتره نسبت به مابقی گزینه‌ها.
۶۰. گزینه دوم. عینا تو کلاس گفته شده بود این و تمرین مرجع هم بود!!!!!!
۶۱. گزینه اول. اولی مرتبه ان میشه. گزینه دوم هر بار داره همه رو از نو محاسبه میکنه سوم و چهارم هم مشخصه مثل دومی عمل میکنه
۶۲. گزینه اول. تو بهینه محلی گیر میکنه و ممکنه جواب بهینه رو برای این مسئله خاص پیدا نکنه. مابقی گزینه‌ها رد میشن چون نسخه‌های خاص‌اش نیاز به حل دقیق نیست و میشه با همین حریصانه جواب بهینه رو بدست آورد.
اساسا این سوال کلی ابهام داره!!!! احتمال حذفش هست به نظرم. چون موارد دوم تا یکی به آخر هم غلط نیستن واقعیت.
۶۳. گزینه سوم. مشابهش تو کلاس بوده
۶۴. گزینه دوم. تو اسلایدهای کلاس بوده عینا
۶۵. گزینه سوم. هرم دوتایی مرتبه حذف درج و حذف مکس میاره روی لاگ‌ان و به کمک داده ساختار مرتب AVL که سایز هر زیر درخت ذخیره کردیم می‌تونیم میانه رو تو لاگ ان پیدا کنیم. با هرم دوتایی هم میانه به راحتی به دست میاد. تمرین MIT بوده.
۶۶. گزینه سوم. اثباتش https://mathcenter.oxford.emory.edu/site/cs171/quickSortAnalysis/#:~:text=Thus%2C%20on%20average%20the%20quick,data%20movement%20during%20the%20sort.
۶۷. گزینه دوم. سایر گزینه‌ها ظاهراً دقیقا به نود 3n/4 خواهند رسید.