۰
subtitle
ارسال: #۱
زمان اجرای Extract-Max برای هیپ d تایی؟
با عرض سلام.
زمان اجرای Extract-Max برای هیپ d تایی از چه مرتبه ای؟
واسه هیپ باینری که از مرتبه[tex]( log_{2}(n))[/tex] میشه. اما واسه هیپ dتایی تو حل المسائل clrs نوشته که میشه [tex]d( log_{d}(n))[/tex]
چرا؟
زمان اجرای Extract-Max برای هیپ d تایی از چه مرتبه ای؟
واسه هیپ باینری که از مرتبه[tex]( log_{2}(n))[/tex] میشه. اما واسه هیپ dتایی تو حل المسائل clrs نوشته که میشه [tex]d( log_{d}(n))[/tex]
چرا؟
۰
ارسال: #۲
RE: زمان اجرای Extract-Max برای هیپ d تایی؟
(۰۱ بهمن ۱۳۸۹ ۰۱:۲۲ ب.ظ)sos006 نوشته شده توسط: با عرض سلام.
زمان اجرای Extract-Max برای هیپ d تایی از چه مرتبه ای؟
واسه هیپ باینری که از مرتبه[tex]( log_{2}(n))[/tex] میشه. اما واسه هیپ dتایی تو حل المسائل clrs نوشته که میشه [tex]d( log_{d}(n))[/tex]
چرا؟
توی الگوریتم هیپ باینری دو تا فرزند وجود داشت و با یک مقایسه ماکزیممشون پیدا میشد ولی توی الگوریتم جدید d تا فرزند هست که برای پیدا کردن ماکزیممشون به [tex]O(d)[/tex] زمان نیاز می باشد.
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close