Phân tích độ phức tạp
Bài học 5 trên 11 trong khóa học Sắp xếp nổi bọt của Coddy.
Phân tích độ phức tạp của thuật toán sắp xếp nổi bọt.
Độ phức tạp thời gian phụ thuộc vào số lần so sánh và hoán đổi được thực hiện.
Ta cần thực hiện n lượt và trong mỗi lượt có (n-1) lần so sánh. Trong đó, n là số phần tử trong danh sách.
Tổng số lần so sánh=(n-1)+(n-1)+(n-1)....n lần
=n*(n-1)
=n2-n
Độ phức tạp thời gian của thuật toán sắp xếp nổi bọt là O(n2).
Nếu xét về độ phức tạp không gian, thuật toán không sử dụng thêm không gian nào. Việc sắp xếp được thực hiện tại chỗ và các phần tử được sắp xếp ngay trong danh sách ban đầu.
Độ phức tạp không gian của thuật toán sắp xếp nổi bọt là O(1) (hằng số).
Thử thách
DễTạo một hàm tên là count_swaps nhận một mảng và kích thước của mảng. Thực hiện thuật toán sắp xếp nổi bọt trên mảng và đếm số lần hoán đổi.
Tự làm thử
#include <stdio.h>
#include <stdlib.h>
int count_swaps(int* arr, int arr_size, int n) {
// Viết code ở đây
return 0;
}
Tất cả bài học trong Sắp xếp nổi bọt
1Kiến thức cơ bản về sắp xếp nổi bọt
Giới thiệuCách hoạt động của sắp xếp nổi bọtHoán đổi các phần tử liền kềThuật toán sắp xếp nổi bọtTự luyện tập: Trình biên dịch C online