دوستان فرق این سه تا سوال چیه؟و چرا جوابا فرق اره؟
۱)میخواهیم دوهیپ مینیمم با اندازه هایn و m را در هیپ به اندازه n+m ادغام کنیم.فرض کنید که هیپ خروجی میتواند به صورت درختی باشد.بافرض n>m کدام یک از گزینه های زیرهمیشه درست است؟
الف)این کار را میتوان همیشه در[tex]O(lg^{2}(n))[/tex]
انجام داد.
ب)این کار راهمیشه میتوان در[tex]O(lgn))[/tex]
انجام داد.
ج)این کار راهمیشه میتوان در[tex]O(lgn))[/tex]
انجام داد.و هیپ خروجی لزوما به صورت آرایه ای نیست.
د)این کار را میتوان همیشه در[tex]O(lg^{2}(n))[/tex]
انجام داد.ولی هیپ خروجی لزوما به صورت آرایه ای نیست.
جواب میشه گزینه۲
۲)اگربخواهیم دوهیپ min-heap به تعدادm وn را باهم ادغام کنیم پیچیدگی زمانی آن برابر است با:
الف)[tex]O(mlgmn))[/tex]
ب)[tex]O(mlgn nlgm))[/tex]
ج)[tex]O(nlgn.lgm))[/tex]
د)[tex]O(m.lgn.lgm))[/tex]
جواب گزینه ۱ میشه.اینو میدونم چه جوری حل میشه.
۳)مرتبه زمانی ادغام دو هیپ چیست؟
این سوال تو یه تاپیک دیگه پرسیده شده و دوستان پاسخ [tex]2n[/tex]
رو دادن.
دوستان تفاوت این ۳سوال در چیه.بی صبرانه منتظرم.با تشکر.
به نظر من بستگی به نظر طراح داره و این یک جور مشکل طراحی سوال هستش
در ادغام بهینه هیپ، که از زمان خطی نسبت به n هست، دو اشاره گر روی دو آرایه
اما اگر اعضا رو یکی یکی پاک کنی از یکی و در دیگری درج کنی لگاریتمی میشه
یه سوال هم من دیدم یه جا که دوتا هیچ رو همینطوری به هم چسبونده بود از مرتبه ۱
پس کلا جدی نگیر
کاملا بستگی به گزینه‌ها داره
تو کتاب پوران گفته شده اگر بخواهیم دوتا هیپو ادغام کنیم مرتبه اجراییش میشه O(n که n مجموع نودهای هردو هیپ هست
حالا باوجود این سوالها و جوابها چه نتیجه ای میشه گرفت؟
(۲۷ بهمن ۱۳۸۹ ۰۱:۰۱ ق.ظ)sal_dovomi نوشته شده توسط: دوستان فرق این سه تا سوال چیه؟و چرا جوابا فرق اره؟
۱)میخواهیم دوهیپ مینیمم با اندازه هایn و m را در هیپ به اندازه n+m ادغام کنیم.فرض کنید که هیپ خروجی میتواند به صورت درختی باشد.بافرض n>m کدام یک از گزینه های زیرهمیشه درست است؟
الف)این کار را میتوان همیشه در[tex]O(lg^{2}(n))[/tex]
انجام داد.
ب)این کار راهمیشه میتوان در[tex]O(lgn))[/tex]
انجام داد.
ج)این کار راهمیشه میتوان در[tex]O(lgn))[/tex]
انجام داد.و هیپ خروجی لزوما به صورت آرایه ای نیست.
د)این کار را میتوان همیشه در[tex]O(lg^{2}(n))[/tex]
انجام داد.ولی هیپ خروجی لزوما به صورت آرایه ای نیست.
جواب میشه گزینه۲
با سلاام
از انجا که ما انواع مختلف هیپ داریم از جمله: :
هیپ دودویی
هیپ فیبونانچی
هیپ دو جمله ایی
و هزینه هر یک از این اعمال هم در این هیپها متفاوت هست
سر فصل دورس کارشناسی تنها هیپ باینری یا دودوی هست اما در مورد اعمال سایر هیپها هم باید اطلاع داشته باشین.
توجه: صورت سئوال تنها به نام هیپ مینیمم بسنده کرده و به هیچ عنوان نوع هیپ رو مشخص نکرده بنابراین با توجه به گزینه‌ها باید نوع هیپ را تشخیص بدهیم .
لذا ما این کاررا میتوانیم :
در هیپ دودویی در زمان[tex]\theta (n)[/tex]
و در هیپ دو جمله ایی در زمان [tex]\theta (lgn)[/tex]
و در هیپ فیپونانچی در زمان [tex]\theta (1)[/tex]
میتوانیم این کار رو انجام دهیم(ادغام دو هیپ) .
و اما در مورد سئوال سوم:
از روی گزینها میتوان تشخیص داد که منظورش در حالت معملی است نه صرفا بهترین جواب والگوریتم مروبطه این است که از یکی حذف کن و به دیگری اضافه کن که هزینه حذف m تا نود برابر با [tex]mLg(m)[/tex] وهزینه درج m تا گره در درخت دیگر هم [tex]mlg(n)[/tex] هست که هزینه کل برابر با مجموع این دو هزینه است .
البته چون در گزینه‌ها همه گزینه بر حسب n و m لگاریتمی است لذا میتوان تشخیص داد که منظور طراح چی بوده است.