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

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

• Trường hợp tốt nhất: O(n)
  • Khi mảng đã được sắp xếp, Insertion Sort chỉ cần duyệt qua một lần để xác nhận thứ tự đã sắp xếp.
• Trường hợp trung bình và xấu nhất: O(n²)
  • Trong trường hợp trung bình và xấu nhất, thuật toán cần thời gian bậc hai vì với mỗi phần tử, ta có thể cần so sánh và dịch chuyển các phần tử trong toàn bộ phần đã sắp xếp.

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

• O(1)
  • Insertion Sort là thuật toán sắp xếp tại chỗ, nghĩa là thuật toán không cần thêm bộ nhớ có kích thước tỷ lệ với đầu vào.
  • Bộ nhớ dùng để sắp xếp luôn không đổi, bất kể kích thước đầu vào.

Tóm tắt:

• Insertion Sort hiệu quả với tập dữ liệu nhỏ hoặc mảng gần như đã được sắp xếp.
• Thuật toán này kém phù hợp với tập dữ liệu lớn vì có độ phức tạp thời gian bậc hai.
• Độ phức tạp không gian không đổi, nên thuật toán tiết kiệm bộ nhớ với mọi kích thước đầu vào.