الگوریتمو ضمیمه کردم
order هر خط رو مشخص کردم بخشایی که داخل کادر قرمز رنگ هست تو تحلیل مرتبش ابهام دارم
تشکر از دوستانی که وقت میذارن.
[attachment=5533]
[attachment=5534]
اگه اون زمان اجرا ها در صورت سوال بوده باشه که فک کنم منظور از خط ۱۱ o(1) رو به این دلیل گذاشته که فرض کرده درخت هیپ به صورت یه آرایه مرتبه و با یه بار دسترسی به اولین خانه کوچکترین عنصر رو پیدا میکنیم و اون عنصر از آرایه حذف میشه و اشاره گر به دومین خانه اشاره میکنه. در مورد زمان اجرا هم فک کنم زمانش v- 1 به توان ۲ در log v بشه که همونطور که خودتون میدونید برای درخت پر میشه همون elogv .
البته فک کنم.
(۲۰ تیر ۱۳۹۱ ۰۷:۲۰ ب.ظ)edge نوشته شده توسط: اگه اون زمان اجرا ها در صورت سوال بوده باشه که فک کنم منظور از خط ۱۱ o(1) رو به این دلیل گذاشته که فرض کرده درخت هیپ به صورت یه آرایه مرتبه و با یه بار دسترسی به اولین خانه کوچکترین عنصر رو پیدا میکنیم و اون عنصر از آرایه حذف میشه و اشاره گر به دومین خانه اشاره میکنه. در مورد زمان اجرا هم فک کنم زمانش v- 1 به توان ۲ در log v بشه که همونطور که خودتون میدونید برای درخت پر میشه همون elogv .ممنون از پاسختون
البته فک کنم.
زمان اجرا هابا توجه به توضیحات توابع هست و فکر نکنم فرضا اگر سوالی مطرح بشه زماناشو بدن.
بخش مربوط به کادر قرمزو اشکال دارم که چطوری به elog v میرسه
Build-heap : ساخت heap با مقادیر پیش فرض key
Extract-Min:کوچکترین مقدار heap را برمیگرداند. که همان ریشه است و سپس دوباره heap رابازسازی میکند.
Decrease-Key:جایگزینی یک مقدار heap با مقدار کوچکتر و بازسازی مجدد heap
مقادیرو از توضیحات نوشتم، داخل کادر قرمزو البته شک دارم. و ابهامم همین قسمته و این که به elog v چطور رسیده.
(۲۰ تیر ۱۳۹۱ ۰۷:۲۰ ب.ظ)edge نوشته شده توسط: زمانش v- 1 به توان ۲ در log v بشه که همونطور که خودتون میدونید برای درخت پر میشه همون elogv .ورودی، گرافه
که بیشترین تعداد یالش میشه
[tex]\begin{pmatrix} v\begin{pmatrix} v-1 \end{pmatrix} \end{pmatrix}/2[/tex]
که البته تو تحلیل الگوریتم فکر نکنم استفاده ای بشه.