Junior — Middle
Tezkor saralash algoritmining eng yomon, o'rtacha va eng yaxshi holatdagi vaqt murakkabligi qanday?
sobes.tech AI
AIdan javob
QuickSort algoritmining vaqt murakkabligi:
- Eng yomon holat: O(n²) — bu, agar pivot element noto'g'ri tanlangan bo'lsa (masalan, har doim eng katta yoki eng kichik element), va massiv noteng bo'linadi.
- O'rtacha holat: O(n log n) — tasodifiy pivot tanlanganda yoki yaxshi bo'linishda.
- Eng yaxshi holat: O(n log n) — har bir bosqichda massiv taxminan teng ikkiga bo'linadi.
Shunday qilib, QuickSort odatda juda samarali ishlaydi, ammo eng yomon holatda kvadrat murakkablikka tushishi mumkin.