اگه الگوریتم دایجکسترا رو با هرم فیبو ناچی حل کنیم جوابش میشه (e+vlogv) میخواستم دلیلش رو بدونم در واقع در هیپ فیبوناچی چه جوری عمل میشه که این مرتبه زمانی بدست میاد.
ممنون میشم اگه از دوستان یکی در این مورد راهنمایی کنه
مرتبه کلی الگوریتم دایکسترا میشه : [tex]O(E\times DecreaseKey V\times ExtractMin)[/tex]
که حالا اگه شما از آرایه استفاده کنی هزینه کاهش کلید میشه ۱ و پیدا کردن مینیموم میشه V
اگه از هیپ عادی استفاده کنی میشه هردوشون lgv
اگه از فیبوناچی استفاده کنیم هزینه کاهش به صورت سرشکن شده از ۱ هست و پیدا کردن مینیموم از Lg v
منبع: ویکیپدیا.
(۱۸ بهمن ۱۳۹۲ ۰۸:۰۴ ب.ظ)Riemann نوشته شده توسط: مرتبه کلی الگوریتم دایکسترا میشه : [tex]O(E\times DecreaseKey V\times ExtractMin)[/tex]ممنون جالب بود
که حالا اگه شما از آرایه استفاده کنی هزینه کاهش کلید میشه ۱ و پیدا کردن مینیموم میشه V
اگه از هیپ عادی استفاده کنی میشه هردوشون lgv
اگه از فیبوناچی استفاده کنیم هزینه کاهش به صورت سرشکن شده از ۱ هست و پیدا کردن مینیموم از Lg v
منبع: ویکیپدیا.
