زمان کنونی: ۰۹ فروردین ۱۴۰۳, ۰۸:۳۰ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

سه سوال مشابه ولی متفاوت

ارسال:
  

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]
انجام داد.ولی هیپ خروجی لزوما به صورت آرایه ای نیست.
جواب میشه گزینه۲


۲)اگربخواهیم دوهیپ 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]
رو دادن.


دوستان تفاوت این ۳سوال در چیه.بی صبرانه منتظرم.با تشکر.

۰
ارسال:
  

javadjj پاسخ داده:

سه سوال مشابه ولی متفاوت

به نظر من بستگی به نظر طراح داره و این یک جور مشکل طراحی سوال هستش

۰
ارسال:
  

bijibuji پاسخ داده:

سه سوال مشابه ولی متفاوت

در ادغام بهینه هیپ، که از زمان خطی نسبت به n هست، دو اشاره گر روی دو آرایه
اما اگر اعضا رو یکی یکی پاک کنی از یکی و در دیگری درج کنی لگاریتمی میشه
یه سوال هم من دیدم یه جا که دوتا هیچ رو همینطوری به هم چسبونده بود از مرتبه ۱
پس کلا جدی نگیر
کاملا بستگی به گزینه‌ها داره

۰
ارسال:
  

narges_r پاسخ داده:

سه سوال مشابه ولی متفاوت

تو کتاب پوران گفته شده اگر بخواهیم دوتا هیپو ادغام کنیم مرتبه اجراییش میشه O(n که n مجموع نودهای هردو هیپ هست
حالا باوجود این سوالها و جوابها چه نتیجه ای میشه گرفت؟

۰
ارسال:
  

hadi_m پاسخ داده:

RE: سه سوال مشابه ولی متفاوت

(۲۷ بهمن ۱۳۸۹ ۰۱:۰۱ ق.ظ)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 لگاریتمی است لذا میتوان تشخیص داد که منظور طراح چی بوده است.



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
Question تفاوت تعداد مقایسه های مورد نیاز در الگوریتم های متفاوت porseshgar ۰ ۱,۹۲۳ ۱۵ بهمن ۱۳۹۷ ۱۲:۳۳ ب.ظ
آخرین ارسال: porseshgar
  ثبت نام مجدد کارشناسی ارشد (در رشته متفاوت) برای فارغ التحصیل کارشناسی ارشد amateurobot ۰ ۱,۹۸۰ ۰۱ اسفند ۱۳۹۶ ۰۹:۳۵ ب.ظ
آخرین ارسال: amateurobot
Question امکان موفقیت برای کسی که دیپلمش ریاضی هست ولی میخواد ارشد هوش مصنوعی یا آی تی بخونه ؟ dashyasin ۹ ۶,۷۷۶ ۲۴ آذر ۱۳۹۶ ۰۳:۲۹ ب.ظ
آخرین ارسال: dashyasin
  رتبه ۴۵۰۰ نرم افزار..(تجربه شخصی متفاوت) Milad_Hosseini ۰ ۲,۷۲۹ ۲۶ خرداد ۱۳۹۶ ۰۲:۲۶ ب.ظ
آخرین ارسال: Milad_Hosseini
  سوال مشابه منطق ارشد ۹۳ arash691 ۲ ۱,۸۵۳ ۰۷ اسفند ۱۳۹۵ ۰۹:۱۲ ب.ظ
آخرین ارسال: arash691
  کلی لغت بلدم ولی چرا.... iCanDoIt ۱۲ ۶,۳۳۰ ۰۸ دى ۱۳۹۴ ۱۲:۰۳ ب.ظ
آخرین ارسال: karbar
  حسگر بلعیدنی با عملکرد مشابه گوشی پزشکی sargonco ۰ ۱,۶۰۶ ۰۱ آذر ۱۳۹۴ ۰۲:۵۹ ب.ظ
آخرین ارسال: sargonco
Tongue سوال مشابه در یک سال با دو جواب مختلف Baranmalihe ۲ ۲,۰۳۵ ۲۸ آبان ۱۳۹۴ ۰۹:۵۱ ب.ظ
آخرین ارسال: Baranmalihe
  جزوه و ویس ابراهیمی مقدم خوبه واسه من که ۶۰ درصد مقسمی رو خوندم ولی اشکال زیاد دارم؟ hamide.m ۳ ۳,۹۵۷ ۱۶ آبان ۱۳۹۴ ۱۱:۲۵ ق.ظ
آخرین ارسال: hamide.m
  گرایش امنیت و شبکه در کنکور ارشد ۹۵ مشابه سالهای پیش است ashki0021 ۲ ۲,۶۱۵ ۱۶ شهریور ۱۳۹۴ ۱۲:۰۵ ب.ظ
آخرین ارسال: popoloo

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close