Junior — Middle
Kāda ir ātrās šķirošanas algoritma laika sarežģītība sliktākajā, vidējā un labākajā gadījumā?
sobes.tech AI
Atbilde no AI
Ātrās šķirošanas (QuickSort) algoritma laika sarežģītība:
- Slikākais gadījums: O(n²) — rodas, kad pivot elements tiek izvēlēti neveiksmīgi (piemēram, vienmēr lielākais vai mazākais elements), un masīvs tiek sadalīts nevienmērīgi.
- Vidējais gadījums: O(n log n) — izvēloties nejaušu pivot vai veicot labu sadalījumu.
- Labākais gadījums: O(n log n) — kad masīvs katrā solī tiek sadalīts apmēram vienādās daļās.
Tādējādi, QuickSort parasti darbojas ļoti efektīvi, bet sliktākajā gadījumā var samazināties līdz kvadrātiskai sarežģītībai.