Phân tích các thuật toán kinh điển

Thuật toán tìm kiếm

Tìm kiếm tuyến tính (Linear Search)

• Linear Search được triển khai bằng cách duyệt từ đầu đến cuối tất cả các phần tử và so sánh nó với giá trị cần tìm. Thuật toán dừng lại khi duyệt hết danh sách hoặc tìm thấy phần tử cần tìm.
• Trường hợp xấu nhất là khi phần tử cần tìm nằm ở cuối danh sách hoặc không tìm thấy phần tử cần tìm. Khi này buộc phải duyệt qua tất cả danh sách.
• Thuật toán có độ phức tạp O(n)

Tìm kiếm nhị phân (Binary Search)

• Binary Search được thực hiện trên một danh sách đã được sắp xếp
• Mảng cần tìm sẽ được chia thành 2 phần left và right, phần tử ở giữa gọi là mid. Dựa vào mid ta xác định xem phần tử cần tìm nằm ở left hoặc right. Loại bỏ phía không chứa phần tử cần tìm rồi lặp lại cho đến khi tìm được phần tử.
• Thuật toán có độ phức tạp là O(log n)

Thuật toán sắp xếp

Sắp xếp nổi bọt (Bubble Sort)

• Bubble Sort được thực hiện bằng cách lặp qua toàn bộ danh sách, so sánh 2 phần tử liền kề và đổi chỗ chúng nếu cần.
• Thuật toán này sử dụng 2 vòng lặp lồng nhau. Vòng ngoài xác định số lượt duyệt, vòng trong thực hiện so sánh và đổi chỗ
• Thuật toán có độ phức tạp là O(n²)

Sắp xếp nhanh (QuickSort)

• QuickSort chọn một phần tử làm pivot sau đó sắp xếp lại mảng sao cho các phần tử lớn hoặc bằng pivot nằm một phía và nhỏ hơn nằm một phía. Tiếp tục đệ quy với 2 danh sách nằm ở 2 phía của pivot. Quá trình được lặp lại đến khi các mảng con chỉ còn 1 phần tử.
• Thuật toán có độ phức tạp là O(n log n) xảy ra khi pivot được chọn gần với giá trị ở giữa danh sách
• Trong trường hợp xấu nhất độ phức tạp là O(n²) xảy ra khi pivot là phần tử lớn nhất hoặc nhỏ nhất.