Độ phức tạp thời gian và không gian

Độ phức tạp thời gian:

• Trường hợp trung bình: O(n log n)
  • Mỗi lần, một chốt cân bằng chia mảng thành hai nửa gần bằng nhau, tạo ra khoảng log n mức phân vùng với độ phức tạp O(n).
• Trường hợp xấu nhất: O(n²)
  • Nếu chốt luôn là phần tử nhỏ nhất hoặc lớn nhất (ví dụ, mảng đã được sắp xếp và chọn phần tử cuối làm chốt), một phía sẽ luôn rỗng và đệ quy sẽ sâu đến n mức.

Độ phức tạp không gian:

• O(n) với phiên bản chúng ta xây dựng ở đây, vì mỗi bước đều tạo ra các danh sách nhỏ hơn và lớn hơn. Quick Sort tại chỗ cổ điển giảm độ phức tạp này xuống còn O(log n) không gian bổ sung.

Tóm tắt:

• Quick Sort rất nhanh trong trường hợp trung bình và là thuật toán sắp xếp được dùng phổ biến trong thực tế.
• Chọn chốt không phù hợp có thể khiến độ phức tạp tăng lên O(n²); các chiến lược chọn chốt tốt (như chọn ngẫu nhiên hoặc chọn phần tử trung vị) sẽ tránh được điều này.