چگونه می توان ثابت کرد که هزینه ساخت یک درخت MinHeap
order of n است
Printable View
چگونه می توان ثابت کرد که هزینه ساخت یک درخت MinHeap
order of n است
هزینه ساختش nlog(n) هستش؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟نقل قول:
نوشته شده توسط Alen
با سلام
ضمن احترام به صحبت دوستمون
باید به اطلاع شما دوستان برسونم که make_heap از مرتبه زمانی n است و باز اگه بخوام دقیق تر بگم ساخت هیپ کوچکتر از 3n است و این یعنی مرتبه n.
البته لازم به ذکر است که در کتابهای ساختمان داده ها همون nlogn رو مطرح می کنن ولی الگوریتمی هست که در مبحث درس طراحی الگوریتم ارائه می شه و از مرتبه زمانی n برخوردار است .
برای اثبات کمی جزئیات نیاز هست اگه علاقه مند بودید یه تاپیک بزارید حتما براتون یادداشت می کنم .
موفق باشید .
میشه کمی توضیح بدید
سلام
الگوریتم زیر رو یه نگاه بندازین
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 نیست
اگر اجازه بدین توی یک فرصت دیگه بقیه اش رو ادامه می دم (ببخشید)
ظاهرا اینجا خیلی خوب نمی شه این ها رو نوشت سعی می کنم با ورد بنویسم بیارم منتظر باشید
جالب بود ولی باز هزینش چندان کم نشده درسته کم شده ولی قابل اغماض ا
نوشتن بقیه کمی وقت گیره اگه کافیه ننویسم در غیر اینصورت اعلام کنید تا کاملش کنم
موفق باشید
نه منظورتو گرفتمنقل قول:
نوشته شده توسط raha_hakhamanesh