Luyện tập thuật toán thực tế
Các Khái Niệm trong Khoa Học Máy Tính
Pritesh Patel
Computer Scientist & Data Scientist for over 20 years
Thuật toán sắp xếp: bubble sort vs quick sort
Bubble Sort
- Bubble Sort: So sánh, hoán đổi, lặp lại, qua lượt.
- Độ phức tạp thời gian: $O(n^2)$.
- Với hàng triệu mặt hàng cần sắp xếp khi mua sắm online – tăng rất nhanh khi danh mục lớn dần.
Quick Sort
- Quick Sort: Chia, chọn chốt, sắp, gộp.
- Độ phức tạp thời gian: O(n log n).
- Với hàng triệu mặt hàng cần sắp xếp – mở rộng bền vững hơn khi danh mục tăng.
Thuật toán tìm kiếm: linear search vs binary search
Linear Search
- Độ phức tạp thời gian: $O(n)$.
- Đơn giản, kiểm tra từng phần tử.
- Linear Search: Quét, so sánh, tìm, dừng.
Binary Search
- Độ phức tạp thời gian: $O(log\,n)$.
- Hiệu quả, nhưng yêu cầu danh sách đã sắp xếp.
- Binary Search: Chia, so sánh, loại, lặp.
