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

Vì sao quan tâm tốc độ? Đếm thao tác

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

Vì sao ta đo tốc độ thuật toán bằng số thao tác chứ không bằng giây, vì sao một thuật toán có thể nhanh gấp hàng chục nghìn lần thuật toán khác cho cùng một bài toán, và một mẹo kinh điển để tăng tốc: đánh đổi bộ nhớ lấy thời gian.

1. Trực quan: hai cách tìm bạn trong danh bạ​

Bạn cần tìm số của "Phúc" trong cuốn danh bạ đã sắp xếp theo tên dày 1000 trang:

  • Cách 1 — lật từng trang từ đầu cho tới khi gặp. Xui thì lật gần 1000 lần.
  • Cách 2 — mở giữa, thấy "Phúc" nằm trước hay sau trang đang mở, bỏ luôn nửa kia, lặp lại. Chỉ khoảng 10 lần mở là ra.

Cùng cuốn danh bạ, cùng đôi tay, nhưng cách 2 nhanh gấp trăm lần. Khác biệt không nằm ở bạn khỏe hay yếu, mà ở cách làm — tức thuật toán. Đây là lý do dân lập trình ám ảnh với thuật toán: đổi cách làm có thể biến "treo máy" thành "tức thì" mà không cần máy mạnh hơn.

2. Vì sao không đo bằng giây?​

Bản năng đầu tiên là bấm giờ: "code chạy 0,3 giây, nhanh!". Nhưng đo bằng giây rất tệ để so sánh thuật toán:

  • Phụ thuộc máy mạnh/yếu — cùng code, máy bạn 0,3s, máy cũ 3s.
  • Phụ thuộc ngôn ngữ — C++ thường nhanh hơn Python nhiều lần cho cùng thuật toán.
  • Phụ thuộc lúc đo — máy đang mở 50 tab thì chậm hơn.

Thay vào đó ta đếm số thao tác cơ bản (so sánh, gán, cộng...) theo kích thước đầu vào, gọi là n. Cách này không phụ thuộc phần cứng và trả lời câu hỏi thật sự quan trọng: khi dữ liệu lớn lên, công việc phình ra cỡ nào?

3. Đếm thao tác: ví dụ "có hai số cộng lại bằng target?"​

Cho mảng số, hỏi: có hai phần tử nào cộng lại đúng bằng target không?

Cách ngây thơ — thử mọi cặp. Bấm Run, để ý biến dem (số phép so sánh):

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

Hai vòng lặp lồng nhau → với mảng n phần tử, số cặp khoảng n²/2. Với n = 10 chỉ ~45 (nhẹ). Nhưng với n = 100.000 thì ~5 tỷ thao tác — máy ì ạch hàng phút.

4. Cùng bài toán, cách nhanh hơn nhiều​

Mẹo: thay vì thử mọi cặp, ta nhớ những số đã thấy trong một tập (set). Với mỗi số x, chỉ cần hỏi "đã thấy target - x chưa?" — tra trong set gần như tức thì. Chỉ duyệt mảng một lần.

Bấm Run rồi so số thao tác với cách trên:

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

Từ ~n² xuống ~n. Với n = 100.000: từ ~5 tỷ xuống ~100.000 thao tác — nhanh gấp khoảng 50.000 lần. Đây là một đánh đổi kinh điển: tốn thêm chút bộ nhớ (cái set) để đổi lấy tốc độ khổng lồ. Bạn sẽ gặp lại mẹo này rất nhiều.

5. Chạy debug: nhìn mẹo "set" hoạt động​

Bước qua từng dòng cách nhanh với A = [2, 4, 3, 5], target = 7. Để ý tập da_thay lớn dần và khoảnh khắc tìm thấy:

🐞 Mẹo set, A = [2, 4, 3, 5], target = 7Bước 1/10
1def co_cap(A, target):
2  da_thay = set()
3  for x in A:
4      if target - x in da_thay:
5          return True
6      da_thay.add(x)
7  return False
Biến tại bước này
da_thay{}
👉 Tập rỗng để nhớ các số đã thấy.

6. Cảm nhận: n² lớn nhanh tới mức nào​

Giả sử mỗi thao tác mất 1 micro-giây (một phần triệu giây):

n~n thao tácthời gian~n² thao tácthời gian
1.0001.000~0,001 giây1.000.000~1 giây
100.000100.000~0,1 giây10 tỷ~2,8 giờ
1.000.0001 triệu~1 giây1.000 tỷ~11 ngày

Khi n lớn, khác biệt giữa n và n² là khác biệt giữa tức thì và bỏ máy chạy qua đêm.

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

  • Vòng lặp lồng vòng lặp trên cùng dữ liệu → cẩn thận, thường ~n².
  • Đổi "thử mọi cặp" thành "nhớ cái đã thấy bằng set/dict" → thường hạ được xuống ~n.
  • Thấy mình đang hỏi đi hỏi lại "đã gặp X chưa?" → nghĩ ngay tới set hoặc dict.

8. 🎮 Trò chơi: Chọn cách nhanh hơn​

Cùng một việc, hai cách làm. Chọn cách nhanh hơn (Big-O nhỏ hơn):

🎮 Chọn cách nhanh hơnCâu 1/4· Điểm 0· 🔥 0

Với mỗi nhiệm vụ, chọn cách có Big-O tốt hơn. Nhớ: O(log n) < O(n) < O(n log n) < O(n²).

Kiểm tra một mảng có phần tử nào bị TRÙNG không?

9. Quiz kiểm tra nhanh​

📝 Quiz kiểm tra nhanh
1. Vì sao đo tốc độ thuật toán bằng số thao tác thay vì giây?
2. Hai vòng lặp lồng nhau duyệt mọi cặp của mảng n phần tử có số thao tác cỡ nào?
3. Mẹo thường dùng để hạ ~n² xuống ~n là gì?

10. Hoàn thành​

…

☑️ Tiếp theo: 1.2.2 — Big-O: ký hiệu & trực giác (đặt tên chính thức cho "~n", "~n²").