Học thuật toán bằng Javascript

[trieu.dev.da]

1. Thuật toán là gì?

• Khi mà giải quyết một bài toán thì thuật toán giúp giải quyết bài toán một cách tốt và hiệu quả nhất.
  Ví dụ: như khi làm việc với lượng dữ liệu lớn, cần thuật toán để tối ưu tốc độ xử lý dữ liệu.
• Cơ bản thường gặp thuật toán tìm kiếm và sắp xếp
  • Thuật toán tìm kiếm một phần tử thỏa mãn điều kiện nào đó trong mảng nhiều phần tử
  • Cho một mảng sắp xếp mảng theo thứ tự tăng dần, giảm dần.

2. Big O notation

• Big O notation là độ phức tạp của thuật toán.
  Ví dụ:
  • O(1): thường tương ứng với một lệnh bình thường
  • O: duyệt vòng lặp for
  • O(n^2): duyệt vòng lặp for lồng vòng lặp for
  • O(logn): duyệt vòng lặp for và xử lý dữ liệu dạng [].push(item)
  • O(n!): trường hợp tệ nhất, có độ phức tạp cao. Sử dụng đệ quy không hợp lý sẽ gặp trường hợp này.
• Theo thứ tự độ phức tạp tăng dần từ O(1) tới O(n!). Độ phức tạp càng thấp thì thuật toán càng tốt.

3. Thuật toán Bubble Sort

• Sắp xếp nổi bọt sẽ đổi vị trí các phần tử với nhau. Phần tử nào lớn (nhỏ) hơn sẽ nổi bọt (đổi chỗ). Lặp lại cho đến khi các phần tử đúng thứ tự.
• Ví dụ các bước chạy thực tế thuật toán bubble sort.

• Code javascript

• Cách viết ngắn gọn

• Độ phức tạp trường hợp xấu nhất: O(n^2). Khá chậm nếu có nhiều dữ liệu.

4. Đổi chỗ 2 phần tử trong mảng theo vị trí

5. Thuật toán selection sort

• Thuật toán Selection Sort sắp xếp một mảng bằng cách liên tục tìm phần tử nhỏ nhất (xét theo thứ tự tăng dần) từ phần chưa được sắp xếp và đặt nó ở đầu. Thuật toán duy trì hai mảng con:
  • Mảng con đã được sắp xếp.
  • Mảng con còn lại chưa được sắp xếp.

• Thuật toán Selection Sort là một thuật toán khá đơn giản khi cài đặt. Thuật toán này có độ phức tạp là O(n2) vì có 2 vòng lặp.