Độ phức tạp về thời gian sắp xếp bong bóng DSA

Xem trang trước để có 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 bong bóng

Thuật toán Bubble Sort sẽ duyệt qua một mảng các giá trị \(n\) \(n-1\) lần trong trường hợp xấu nhất.

Lần đầu tiên thuật toán chạy qua mảng, mọi giá trị sẽ được so sánh với giá trị tiếp theo và hoán đổi các giá trị nếu giá trị bên trái lớn hơn giá trị bên phải. Điều này có nghĩa là giá trị cao nhất sẽ nổi lên và 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 quá trình 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 so sánh và hoán đổi các giá trị.

Chúng ta có thể bắt đầu tính số thao tác được thực hiện bằng thuật toán Bubble Sort trên các giá trị \(n\):

\[Hoạt động = (n-1)\cdot \frac{n}{2} = \frac{n^2}{2} - \frac{n}{2} \]

Khi xem xét độ phức tạp về thời gian của các 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\), thuật ngữ \(\frac{n^2}{2}\) trở nên lớn hơn rất nhiều so với thuật ngữ \(\frac{n}{2}\). Trên thực tế, lớn đến mức chúng ta có thể ước chừ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 \ ]

Khi chúng ta xem xét độ phức tạp về thời gian như chúng ta đang ở đây, sử dụng ký hiệu Big O, các thừa số sẽ bị bỏ qua, do đó thừa số \(\frac{1}{2}\) bị bỏ qua. Điều này có nghĩa là thời gian chạy của thuật toán Bubble Sort có thể được mô tả với độ phức tạp về thời gian bằng cách sử dụng ký hiệu Big O như sau:

\[ O( \frac{1}{2} \cdot n^2) = \underline{\underline{O(n^2)}} \]

Và biểu đồ mô tả độ phức tạp về thời gian của Bubble Sort trông như thế này:

Như bạn có thể thấy, thời gian chạy tăng rất nhanh khi kích thước của mảng tăng lên.

May mắn thay, có những thuật toán sắp xếp nhanh hơn thuật toán này, chẳng hạn như Quicksort .

Mô phỏng sắp xếp bong bóng

Chọn số lượng giá trị trong một mảng và chạy mô phỏng này để xem số lượng thao tác Bubble Sort cần trên một mảng các phần tử \(n\) là \(O(n^2)\):

Đường màu đỏ ở trên biểu thị độ phức tạp thời gian giới hạn trên \(O(n^2)\) và hàm thực tế trong trường hợp này là \(1.05 \cdot n^2\).

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)\) cho một số lượng lớn các giá trị \(n\).

Trong trường hợp này \(f(n)\) là số thao tác được Buble Sort sử dụng, \(g(n)=n^2\) và \(C=1.05\).

Đọc thêm về ký hiệu Big O và độ phức tạp về thời gian trên trang này .