با عرض سلام.
زمان اجرای Extract-Max برای هیپ d تایی از چه مرتبه ای؟
واسه هیپ باینری که از مرتبه[tex]( log_{2}(n))[/tex] میشه. اما واسه هیپ dتایی تو حل المسائل clrs نوشته که میشه [tex]d( log_{d}(n))[/tex]
چرا؟
(۰۱ بهمن ۱۳۸۹ ۰۱:۲۲ ب.ظ)sos006 نوشته شده توسط: با عرض سلام.
زمان اجرای Extract-Max برای هیپ d تایی از چه مرتبه ای؟
واسه هیپ باینری که از مرتبه[tex]( log_{2}(n))[/tex] میشه. اما واسه هیپ dتایی تو حل المسائل clrs نوشته که میشه [tex]d( log_{d}(n))[/tex]
چرا؟
توی الگوریتم هیپ باینری دو تا فرزند وجود داشت و با یک مقایسه ماکزیممشون پیدا میشد ولی توی الگوریتم جدید d تا فرزند هست که برای پیدا کردن ماکزیممشون به [tex]O(d)[/tex] زمان نیاز می باشد.