Chuyển tới nội dung chính

Thuật toán là gì?

Bạn sẽ học được gì

Thuật toán thật ra là gì, một dãy bước phải thỏa những tính chất nào mới được gọi là thuật toán, và cách mô tả nó bằng pseudocode (mã giả) trước khi viết code thật. Bạn cũng sẽ "chạy debug" một thuật toán từng bước để thấy nó hoạt động ra sao bên trong.

1. Trực quan: thuật toán là một "công thức nấu ăn"​

Một công thức nấu phở là: dãy bước rõ ràng, làm đúng thứ tự thì ra tô phở. Nó nhận nguyên liệu (đầu vào) và cho ra món ăn (đầu ra). Ai làm theo cũng ra kết quả giống nhau.

Thuật toán y hệt vậy, chỉ khác là "nguyên liệu" là dữ liệu và "món ăn" là kết quả:

ĐẦU VÀO  ──▶  [ THUẬT TOÁN: dãy bước rõ ràng ]  ──▶  ĐẦU RA
(vd: mảng số)      (so sánh, lặp, cập nhật...)        (vd: số lớn nhất)

Điểm mấu chốt: thuật toán phải rõ ràng tới mức một cái máy không biết suy nghĩ cũng làm theo được. Không có chỗ cho "ước chừng", "tùy cảm hứng".

2. Năm tính chất của một thuật toán​

Không phải dãy bước nào cũng là thuật toán. Phải đủ 5 tính chất:

  1. Đầu vào — nhận 0 hoặc nhiều giá trị vào.
  2. Đầu ra — sinh ra ít nhất 1 kết quả.
  3. Xác định — mỗi bước rõ ràng, không mơ hồ. (Không được kiểu "lấy khoảng một nắm".)
  4. Hữu hạn — phải dừng sau hữu hạn bước. (Không lặp vô tận.)
  5. Hiệu quả — mỗi bước đủ đơn giản để thực hiện được trong thực tế.

Ví dụ KHÔNG phải thuật toán tốt:

  • "Thử ngẫu nhiên các đáp án cho tới khi may mắn đúng." → vi phạm tính xác định và không đảm bảo hữu hạn (có thể chạy mãi mãi không trúng).
  • "Tính số nguyên tố lớn nhất." → vi phạm hữu hạn (không có số nguyên tố lớn nhất, chạy vô tận).
Phân biệt quan trọng

Một thuật toán phải chắc chắn cho ra đáp án đúng sau hữu hạn bước. "Cứ thử cho tới khi được" không phải thuật toán đáng tin.

3. Mô tả bằng pseudocode (mã giả)​

Trước khi viết code thật (Python, C++, Java...), ta phác ý tưởng bằng pseudocode — ngôn ngữ nửa người nửa máy, không phụ thuộc ngôn ngữ lập trình nào. Nó giúp tập trung vào ý tưởng thay vì cú pháp. Ví dụ "tìm số lớn nhất trong mảng":

HÀM tìm_max(mảng A):
    max ← A[0]                  # tạm coi phần tử đầu là lớn nhất
    VỚI MỖI x trong A:
        NẾU x > max:            # gặp số lớn hơn
            max ← x             # cập nhật
    TRẢ VỀ max

Cùng ý tưởng đó dưới dạng sơ đồ khối (flowchart) — nhìn được luồng đi:

   ┌─────────────┐
   │ max = A[0]  │
   └──────┬──────┘
          ▼
   ┌─────────────┐   còn phần tử
   │ duyệt x ∈ A │◀──────────────┐
   └──────┬──────┘                │
          ▼                        │
   ┌─────────────┐   đúng   ┌──────────────┐
   │  x > max ?  │────────▶ │  max = x     │
   └──────┬──────┘          └──────┬───────┘
          │ sai                    │
          ▼◀───────────────────────┘
   ┌─────────────┐
   │ trả về max  │
   └─────────────┘

4. Chạy debug: xem thuật toán "sống dậy" từng bước​

Lý thuyết là vậy, nhưng để thấy nó chạy, hãy bước qua từng dòng với mảng [3, 9, 2, 11, 7]. Để ý biến max_val cập nhật khi gặp số lớn hơn. Bấm ▶ Tự chạy hoặc Tiến ▶:

🐞 Tìm số lớn nhất, A = [3, 9, 2, 11, 7]Bước 1/11
1def tim_max(A):
2  max_val = A[0]
3  for x in A:
4      if x > max_val:
5          max_val = x
6  return max_val
Biến tại bước này
max_val3
👉 Coi phần tử đầu (3) là lớn nhất tạm thời.

5. Code mẫu (chạy thật)​

Dịch pseudocode sang Python — bấm Run để chạy thật, rồi thử đổi mảng xem sao:

Đang tải trình chạy code…

6. Độ phức tạp (gợi mở)​

Thuật toán trên duyệt mỗi phần tử đúng một lần → với mảng n phần tử cần khoảng n phép so sánh. Ta gọi đó là O(n). Vì sao tốc độ quan trọng và O(n) nghĩa là gì, học ở hai bài tiếp theo.

7. Mẫu nhận diện​

  • Cần một đáp án từ một dãy dữ liệu → thường có một vòng lặp "quét qua" toàn bộ.
  • Giữ một biến trạng thái cập nhật dần khi duyệt (ở đây là max_val) — mẫu cực kỳ phổ biến, bạn sẽ gặp lại ở đếm, tính tổng, tìm min/max, tìm phần tử...

8. 🎮 Trò chơi: Đoán đầu ra​

Đọc code rồi đoán kết quả in ra. Tự "chạy trong đầu" như cái máy nhé!

🎮 Đoán đầu raCâu 1/4· Điểm 0· 🔥 0

Tự nhẩm từng bước như debugger ở phần 4, rồi chọn đáp án.

Dãy bước nào KHÔNG phải thuật toán hợp lệ?

9. Quiz kiểm tra nhanh​

📝 Quiz kiểm tra nhanh
1. Tính chất nào BẮT BUỘC để một dãy bước là thuật toán?
2. Pseudocode dùng để làm gì?
3. Thuật toán tìm_max duyệt mảng n phần tử mất bao nhiêu phép so sánh?

10. Hoàn thành​

…

☑️ Tiếp theo: 1.2.1 — Vì sao quan tâm tốc độ?