هزینه ساخت یک درخت MinHeap

[Alen]

چگونه می توان ثابت کرد که هزینه ساخت یک درخت MinHeap
order of n است

[mohandese_hiclass]

چگونه می توان ثابت کرد که هزینه ساخت یک درخت MinHeap
order of n است
هزینه ساختش nlog(n) هستش؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟

[raha_hakhamanesh]

با سلام
ضمن احترام به صحبت دوستمون
باید به اطلاع شما دوستان برسونم که make_heap از مرتبه زمانی n است و باز اگه بخوام دقیق تر بگم ساخت هیپ کوچکتر از 3n است و این یعنی مرتبه n.
البته لازم به ذکر است که در کتابهای ساختمان داده ها همون nlogn رو مطرح می کنن ولی الگوریتمی هست که در مبحث درس طراحی الگوریتم ارائه می شه و از مرتبه زمانی n برخوردار است .
برای اثبات کمی جزئیات نیاز هست اگه علاقه مند بودید یه تاپیک بزارید حتما براتون یادداشت می کنم .
موفق باشید .

[mohandese_hiclass]

میشه کمی توضیح بدید

[raha_hakhamanesh]

سلام
الگوریتم زیر رو یه نگاه بندازین

make_heap
for i=n div 2 downto 1 do
siftdown(i
-------------------------------------------------------------
روال سیفت دان هم بصورت زیر است

SiftDown(i
k=i
repeat
j=k
if 2j<=n and T[2j] >T[K] then k=2j
if 2j< n and T[2j+1] >T[K] then k=2j+1
exchange T[j],T[k
until j=k
end siftdown

خوب حالا می مونه تحلیل اینها
در روال make heap یک ضریب n/2 داریم در مقدار زمان سیفت دان کل زمان رو می ده پس تا اینجا n/2 یادتون باشه
در سیفت دان برای محاسبه تعداد تکرار حقه repeat یک بارومتر خوب باید انتخاب کنیم که j است
در هر مرحله j دو برابر مرحله قبل می شه حالا اگر فرض کنیم تعدادگردش حلقه حداکثر m باشد داریم
n>=2 jm >=4 j m-1 >= ... >= 2 pow(m-1)j
که آخرین j برابر آخرین مقدار ارسالی توسط makeheapیعنی i=1می باشد
بنابراین داریم
n>= 2 pow(m-1) * i
n/i >= 2 pow (m-1
m-1 <= log (n/i
m< log n/i +1
پس یک سقف خوب یافتیم اما این سقف انحصارا بر مبنای n نیست

اگر اجازه بدین توی یک فرصت دیگه بقیه اش رو ادامه می دم (ببخشید)

ظاهرا اینجا خیلی خوب نمی شه این ها رو نوشت سعی می کنم با ورد بنویسم بیارم منتظر باشید

[mohandese_hiclass]

جالب بود ولی باز هزینش چندان کم نشده درسته کم شده ولی قابل اغماض ا

[raha_hakhamanesh]

نوشتن بقیه کمی وقت گیره اگه کافیه ننویسم در غیر اینصورت اعلام کنید تا کاملش کنم
موفق باشید

[mohandese_hiclass]

نوشتن بقیه کمی وقت گیره اگه کافیه ننویسم در غیر اینصورت اعلام کنید تا کاملش کنم
موفق باشید
نه منظورتو گرفتم