|
Oʻzbekiston respublikasi oliy va o‘rta maxsusta’lim vazirligi
|
| bet | 11/16 | | Sana | 15.11.2023 | | Hajmi | 29,81 Mb. | | #99092 |
Bog'liq Dilshoda Algoritm mustaqil QuickSort tahlili:
QuickSort tomonidan olingan vaqt, umuman olganda, quyidagicha yozilishi mumkin.
T(n) = T(k) + T(nk-1) + (n)
Birinchi ikki shart ikkita rekursiv qo'ng'iroqlar uchun, oxirgi atama bo'lish jarayoni uchun. k - pivotdan kichikroq elementlar soni.
Eng yomon holat:
Eng yomon holat, bo'linish jarayoni doimo birinchi yoki oxirgi elementni pivot sifatida tanlaganida sodir bo'ladi. Agar oxirgi element har doim pivot sifatida tanlanadigan yuqoridagi bo'lim strategiyasini ko'rib chiqsak, eng yomon holat massiv allaqachon ortish yoki kamayish tartibida tartiblangan bo'lsa sodir bo'ladi. Quyida eng yomon holatning takrorlanishi keltirilgan.
T(N) = T(0) + T(N-1) + (N ) T(N) = T(N-1) + (N) ga ekvivalent.
Yuqoridagi takrorlanishning yechimi O(n 2 ).
Eng yaxshi holat:
Eng yaxshi holat, bo'linish jarayoni har doim o'rta elementni pivot sifatida tanlaganida sodir bo'ladi. Quyida eng yaxshi holat uchun takrorlanish keltirilgan.
T(N) = 2T(N/2) + (N)
Yuqoridagi takrorlanish uchun yechim O(N * logN) dir. Buni asosiy teoremaning 2-holatidan foydalanib hal qilish mumkin .
O'rtacha holat:
O'rtacha vaziyatni tahlil qilish uchun biz massivning barcha mumkin bo'lgan almashtirishlarini hisobga olishimiz va oson ko'rinmaydigan har bir almashtirish vaqtini hisoblashimiz kerak.
Bo'lim O(N/9) elementlarni bir to'plamga va O(9N/10) elementlarni boshqa to'plamga qo'yish hollarini ko'rib chiqsak, o'rtacha holat haqida tasavvurga ega bo'lishimiz mumkin. Quyida ushbu holatning takrorlanishi keltirilgan.
T(N) = T(N/9) + T(9N/10) + (N)
Yuqoridagi takrorlanishning yechimi ham O(N * logN):
QuickSort-ning eng yomon vaqt murakkabligi O(N 2 ) bo'lsa-da, bu Birlashtirish Saralash va Uyma Saralash kabi ko'plab boshqa saralash algoritmlariga qaraganda ko'proq bo'lsa-da , QuickSort amalda tezroq, chunki uning ichki tsikli ko'pgina arxitekturalarda va ko'pchilik realda samarali amalga oshirilishi mumkin. - dunyo ma'lumotlari. QuickSort turli yo'llar bilan pivot tanlovini o'zgartirish orqali amalga oshirilishi mumkin, shunda ma'lum bir turdagi ma'lumotlar uchun eng yomon holat kamdan-kam uchraydi. Biroq, ma'lumotlar katta bo'lsa va tashqi xotirada saqlangan bo'lsa, birlashtirish tartibi odatda yaxshiroq hisoblanadi.
|
| |
