تالار گفتمان مانشت
سوال درباره Bionamial Heap و الگوریتم پارتیشن Hoare - نسخه‌ی قابل چاپ
سوال درباره Bionamial Heap و الگوریتم پارتیشن Hoare - zerocool_ir - 30 آبان ۱۳۹۲ ۰۸:۰۲ ب.ظ

با سلام خدمت تمامی اساتید گرامی
۲تا سوال داشتم که ذهن من را درگیر کرده ؛ سپاسگذار خواهم شد که پاسخ اساتید محترم را در مورد این ۲ مسئله بشنوم.

۱) در هیپ دو جمله ای یا همان Bionamial Heap چرا مرتبه عمل (findmin = O(Log N می باشد ؟

۲) آنطوری که من از کتاب ClRS خواندم در الگوریتم partition تکنیک Hoare ایشان در ابتدا pivot را عنصر اول قرار داده و i را متغیری با مقداری کمتر از خانه اول آرایه و j را متغیری با مقداری بیشتر از خانه آخر آرایه قرار داده اند .
اما در ۲ کتاب پارسی ساختمان داده پوران و پارسه هر دو مولف i را برابر خانه اول آرایه قرار داده اند .یعنی همان موقعیت pivot
مشکلی که در این حالت پیش می آید اینست که اگر آرایه مرتب نزولی باشد با توجه به حلقه زیر الگوریتم در حلقه بی نهایت می افتد ؛ به نظر شما
اساتید این مقدار دهی i درست است؟
repeat
i=i+1
until A[i] >= pivot


با تشکر از تمامی اساتید

RE: سوال درباره Bionamial Heap و الگوریتم پارتیشن Hoare - mfXpert - 01 آذر ۱۳۹۲ ۰۵:۱۱ ب.ظ

در مورد سوال دوم:

الگوریتمی که برای partition تو کتاب CLRS استفاده شده با روش Hoare کاملا‌ً فرق داره. در نتیجه لزومی نداره متغیرها رو همون طور مقدار بده که در روش Hoare مقداردهی میشن.

RE: سوال درباره Bionamial Heap و الگوریتم پارتیشن Hoare - zerocool_ir - 05 دى ۱۳۹۲ ۰۳:۵۴ ب.ظ

(۰۱ آذر ۱۳۹۲ ۰۵:۱۱ ب.ظ)mfXpert نوشته شده توسط:  در مورد سوال دوم:

الگوریتمی که برای partition تو کتاب CLRS استفاده شده با روش Hoare کاملا‌ً فرق داره. در نتیجه لزومی نداره متغیرها رو همون طور مقدار بده که در روش Hoare مقداردهی میشن.

آنطوری که من دیدم هر دو روش را در کتاب CLRS توضیح داده و کاملا هم اشاره شده که روش توضیح داده شده Hoare است و نکته این هست که این دو کتاب (پوران و پارسه) تمام این الگوریتم را مشابه CLRS نوشته اند ولی بجز همین یک انتساب

Re: سوال درباره Bionamial Heap و الگوریتم پارتیشن Hoare - hoomanab - 05 دى ۱۳۹۲ ۱۰:۱۸ ب.ظ

سوال ۱ این قسمت مربوط به کتاب مدرسانه
[تصویر: 232898_uze9u3em.jpg]
[تصویر: 232898_uzy5ysu6.jpg]

Sent from my SM-T210R using Tapatalk