Độ phức tạp về thời gian sắp xếp lựa 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 thời gian sắp xếp lựa chọn
Thuật toán Sắp xếp lựa chọn đi qua tất cả các phần tử trong một mảng, tìm giá trị thấp nhất và di chuyển nó lên đầu mảng và thực hiện lặp đi lặp lại việc này cho đến khi mảng được sắp xếp.
Sắp xếp lựa chọn đi qua một mảng các giá trị \(n\) \(n-1\) lần. Điều này là do khi thuật toán đã sắp xếp tất cả các giá trị ngoại trừ giá trị cuối cùng thì giá trị cuối cùng cũng phải ở đúng vị trí của nó.
Lần đầu tiên thuật toán chạy qua mảng, mọi giá trị sẽ được so sánh để tìm ra giá trị nào thấp nhất.
Lần thứ hai thuật toán chạy qua mảng, mọi giá trị ngoại trừ giá trị đầu tiên sẽ được so sánh để tìm ra giá trị nào thấp nhất.
Và bằng cách này, phần chưa được sắp xếp của mảng sẽ ngày càng ngắn hơn cho đến khi việc sắp xếp hoàn tất. Vì vậy, trung bình, các phần tử \(\frac{n}{2}\) được xem xét khi thuật toán đi qua mảng để tìm giá trị thấp nhất và di chuyển nó lên phía trước mảng.
Ngoài tất cả các so sánh cần thiết, số lần hoán đổi cần thiết là \(n \).
Chúng ta có thể bắt đầu tính số thao tác cho thuật toán Sắp xếp lựa chọn:
\[ \begin{equation} \begin{aligned} Phép toán {} & = (n-1)\cdot \frac{n}{2} + n \\ & = \frac{n^2}{2} - \ frac{n}{2} + n \\ & = \frac{n^2}{2} + \frac{n}{2} \end{aligned} \end{equation} \]
Khi xem xét thời gian chạy của thuật toán, chúng tôi xem xét các tập dữ liệu rất lớn, nghĩa là \(n\) là một con số rất lớn. Và đối với một số rất lớn \(n\), số hạng \(\frac{n^2}{2}\) trở nên lớn hơn rất nhiều so với số hạng \(\frac{n}{2}\) mà chúng ta có thể gần đúng bằng cách loại bỏ số hạng thứ hai đó \(\frac{n}{2}\).
\[Hoạt động = \frac{n^2}{2} + \frac{n}{2} \approx \frac{n^2}{2} = \frac{1}{2} \cdot n^2 \ ]
Sử dụng ký hiệu Big O để mô tả độ phức tạp về thời gian của thuật toán Sắp xếp lựa chọn, chúng ta nhận được:
\[ O( \frac{1}{2} \cdot n^2) = \underline{\underline{O(n^2)}} \]
Và độ phức tạp về thời gian của thuật toán Sắp xếp lựa chọn có thể được hiển thị trong biểu đồ như sau:
Như bạn có thể thấy, thời gian chạy cũng giống như Bubble Sort: Thời gian chạy tăng rất nhanh khi kích thước của mảng tăng lên.
Mô phỏng sắp xếp lựa chọn
Chạy mô phỏng cho số lượng giá trị khác nhau trong một mảng và xem số lượng thao tác Sắp xếp lựa chọn cần trên một mảng các phần tử \(n\) là \(O(n^2)\):
{{ this.userX }}
Hoạt động: {{ hoạt động }}
Sự khác biệt đáng kể nhất so với Sắp xếp nổi bọt mà chúng ta có thể nhận thấy trong mô phỏng này là trường hợp tốt nhất và xấu nhất thực sự gần giống nhau đối với Sắp xếp lựa chọn (\(O(n^2)\)), nhưng đối với Sắp xếp bong bóng thời gian chạy trường hợp tốt nhất là chỉ \(O(n)\).
Sự khác biệt trong trường hợp tốt nhất và xấu nhất đối với Sắp xếp lựa chọn chủ yếu là số lần hoán đổi. Trong trường hợp tốt nhất, Sắp xếp lựa chọn không phải hoán đổi bất kỳ giá trị nào vì mảng đã được sắp xếp. Và trong trường hợp xấu nhất, khi mảng đã được sắp xếp nhưng sai thứ tự, vì vậy Sắp xếp lựa chọn phải thực hiện nhiều lần hoán đổi bằng số giá trị trong mảng.
