سلام
ادغام دو آرایه در ساختمان داده های مختلف چه مرتبه ی زمانی دارند؟
مثلا در هیپ ، آرایه های مرتب ، درخت جستجوی دودوئی و......
ادغام k آرایه با n عنصر از مرتبه‌ی [tex]O(nLogK)[/tex] هست. حالا شما 2 تا آرایه دارید به جای K عدد 2 رو بزارید میشه از [tex]O(n)[/tex] .
دوستان اگر اشتباه میکنم لطفا تصحیح کنن.
فرقی نداره با چه ساختمان داده ای؟
ببین. در کل برای ادغام K آرایه‌ی مرتب با n عنصر دو روش داریم:
۱) روش عمومی که عنصر اول همه‌ی K آرایه رو با هم مقایسه میکنیم و Min اونها رو انتخاب میکنیم و میشه اولین عنصرِ آرایه‌ی جدیدمون و به همین ترتیب الی آخر. این روش از [tex]O(nk)[/tex] هست.
2) روش دوم با استفاده از هیپ انجام میشه. که از [tex]O(nLogK)[/tex] هست.
واضحه که روش دوم مرتبه‌ی زمانیش بهتر از روش اوله و بنابراین روش بهتریه.