Độ phức tạp về thời gian sắp xếp chèn DSA
Xem trang này để biết giải thích chung về độ phức tạp của thời gian.
Độ phức tạp của thời gian sắp xếp chèn
Trường hợp xấu nhất đối với Sắp xếp chèn là nếu mảng đã được sắp xếp nhưng trước tiên phải có giá trị cao nhất. Đó là vì trong trường hợp như vậy, mọi giá trị mới phải "di chuyển qua" toàn bộ phần được sắp xếp của mảng.
Đây là các thao tác được thực hiện bằng thuật toán Sắp xếp chèn cho các phần tử đầu tiên:
- Giá trị thứ 1 đã ở đúng vị trí.
- Giá trị thứ 2 phải được so sánh và di chuyển qua giá trị thứ 1.
- Giá trị thứ 3 phải được so sánh và di chuyển qua hai giá trị.
- Giá trị thứ 3 phải được so sánh và di chuyển qua ba giá trị.
- Và như thế..
Nếu chúng ta tiếp tục mẫu này, chúng ta sẽ nhận được tổng số thao tác cho các giá trị \(n\):
\[1+2+3+...+(n-1)\]
Đây là một chuỗi nổi tiếng trong toán học có thể được viết như thế này:
\[ \frac{n(n-1)}{2} = \frac{n^2}{2} - \frac{n}{2} \]
Đối với \(n\) rất lớn, số hạng \(\frac{n^2}{2}\) chiếm ưu thế, vì vậy chúng ta có thể đơn giản hóa bằng cách loại bỏ số hạng thứ hai \(\frac{n}{2}\).
Sử dụng ký hiệu Big O, chúng tôi nhận được độ phức tạp về thời gian này đối với thuật toán Sắp xếp chèn:
\[ O(\frac{n^2}{2}) = O(\frac{1}{2} \cdot n^2) = \underline{\underline{O(n^2)}} \]
Độ phức tạp về thời gian có thể được hiển thị như thế này:
Như bạn có thể thấy, thời gian sử dụng của Sắp xếp chèn tăng nhanh khi số lượng giá trị \(n\) tăng lên.
Mô phỏng sắp xếp chèn
Sử dụng mô phỏng bên dưới để xem độ phức tạp về mặt lý thuyết \(O(n^2)\) (đường màu đỏ) so với số lượng thao tác của Sắp xếp chèn thực tế.
{{ this.userX }}
Hoạt động: {{ hoạt động }}
Đối với Sắp xếp chèn, có sự khác biệt lớn giữa các trường hợp tốt nhất, trung bình và trường hợp xấu nhất. Bạn có thể thấy điều đó bằng cách chạy các mô phỏng khác nhau ở trên.
Đường màu đỏ ở trên biểu thị độ phức tạp thời gian giới hạn trên theo lý thuyết \(O(n^2)\) và hàm thực tế trong trường hợp này là \(1.07 \cdot n^2\).
Hãy nhớ rằng hàm \(f(n)\) được gọi là \(O(g(n))\) nếu chúng ta có hằng số dương \(C\) sao cho \(C \cdot g(n)> f(n)\).
Trong trường hợp này \(f(n)\) là số thao tác được sử dụng bởi Sắp xếp chèn, \(g(n)=n^2\) và \(C=1.07\).