|
Chiqishi
Berilgan massiv: 12 11 13 5 6 7
Saralangan massiv: 5 6 7 11 12 13
Vaqt murakkabligi
|
| bet | 15/16 | | Sana | 15.11.2023 | | Hajmi | 29,81 Mb. | | #99092 |
Bog'liq Dilshoda Algoritm mustaqilChiqishi
Berilgan massiv: 12 11 13 5 6 7
Saralangan massiv: 5 6 7 11 12 13
Vaqt murakkabligi: O(N log(N)), Turli mashinalarda massivlarni saralash. Birlashtirish tartibi rekursiv algoritmdir va vaqt murakkabligi quyidagi takrorlanish munosabati sifatida ifodalanishi mumkin.
T(n) = 2T(n/2) + th(n)
Yuqoridagi takrorlanishni takrorlash daraxti usuli yoki Master usuli yordamida hal qilish mumkin. U asosiy usulning II holatiga to'g'ri keladi va takrorlanishning yechimi th(Nlog(N)) dir. Birlashtirish tartiblashning vaqt murakkabligi 3 ta holatda (eng yomon, o'rtacha va eng yaxshi) isth(Nlog(N)) sifatida birlashma tartiblash har doim massivni ikkiga bo'ladi va ikkita yarmini birlashtirish uchun chiziqli vaqt talab etiladi.
Yordamchi bo'shliq: O(n), Birlashtirish tartibida barcha elementlar yordamchi massivga ko'chiriladi. Shunday qilib, birlashtirish uchun N yordamchi bo'sh joy talab qilinadi.
Merge sortni tahlil qilish:
Merge sortkirish ustidan bir nechta o'tishlardan iborat. Birinchi o'tish 1 o'lchamdagi segmentlarni birlashtiradi, ikkinchisi 2 o'lchamdagi segmentlarni va o'tish o'lchami 2 i-1 segmentlarini birlashtiradi . Shunday qilib, o'tishlarning umumiy soni [ log 2 n ] ga teng. Birlashtirish ko'rsatilgandek, biz ikkita tartiblangan segmentni chiziqli vaqtda birlashtira olamiz, ya'ni har bir o'tish O(n) vaqtini oladi. [ log 2 n ] o'tishlar mavjud bo'lganligi sababli , umumiy hisoblash vaqti O(nlogn) ga teng .
Merge sortniing afzalliklari:
Barqarorlik : Birlashtirish tartibi barqaror tartiblash algoritmidir, ya'ni u kirish massividagi teng elementlarning nisbiy tartibini saqlaydi. Bu uni teng elementlarning asl tartibini saqlash muhim bo'lgan ilovalarda foydali qiladi.
Kafolatlangan eng yomon ishlash: Birlashtirish tartibi eng yomon vaqt murakkabligi O(n log n) ga ega, ya'ni u hatto katta ma'lumotlar to'plamlarida ham yaxshi ishlaydi. Boshqa saralash algoritmlari, masalan, tezkor saralash, eng yomon vaqt murakkabligi O(n^2) ga ega, bu esa katta maʼlumotlar toʻplamlarida yomon ishlashga olib kelishi mumkin.
|
| |
