ادغام - نسخهی قابل چاپ |
ادغام - zfmo - 15 دى ۱۳۹۱ ۱۰:۱۳ ب.ظ
سلام ادغام دو آرایه در ساختمان داده های مختلف چه مرتبه ی زمانی دارند؟ مثلا در هیپ ، آرایه های مرتب ، درخت جستجوی دودوئی و...... |
ادغام - Amir V - 16 دى ۱۳۹۱ ۰۲:۲۵ ب.ظ
ادغام k آرایه با n عنصر از مرتبهی [tex]O(nLogK)[/tex] هست. حالا شما ۲ تا آرایه دارید به جای K عدد ۲ رو بزارید میشه از [tex]O(n)[/tex] . دوستان اگر اشتباه میکنم لطفا تصحیح کنن. |
ادغام - zfmo - 16 دى ۱۳۹۱ ۱۰:۵۹ ب.ظ
فرقی نداره با چه ساختمان داده ای؟ |
ادغام - Amir V - 17 دى ۱۳۹۱ ۱۲:۴۲ ق.ظ
ببین. در کل برای ادغام K آرایهی مرتب با n عنصر دو روش داریم: ۱) روش عمومی که عنصر اول همهی K آرایه رو با هم مقایسه میکنیم و Min اونها رو انتخاب میکنیم و میشه اولین عنصرِ آرایهی جدیدمون و به همین ترتیب الی آخر. این روش از [tex]O(nk)[/tex] هست. ۲) روش دوم با استفاده از هیپ انجام میشه. که از [tex]O(nLogK)[/tex] هست. واضحه که روش دوم مرتبهی زمانیش بهتر از روش اوله و بنابراین روش بهتریه. |