Algorithmic efficiency · Hiệu suất thuật toán
What we'll do
- Two programs can both be correct but take very different time.
- This lesson is about efficiency: how the work grows as the input grows.
- Read and think about the ideas; then a few short tasks let you count the steps yourself.
Những gì chúng ta sẽ làm
- Hai chương trình có thể đều đúng nhưng mất thời gian chạy rất khác nhau.
- Bài học này nói về hiệu suất: cách khối lượng công việc tăng lên khi dữ liệu đầu vào tăng lên.
- Đọc và suy nghĩ về các ý tưởng; sau đó vài nhiệm vụ ngắn gọn cho phép bạn đếm số bước chính mình.
Counting the work
- We measure an algorithm by how many steps it does, not seconds.
- Steps in seconds depend on the computer; counting steps does not.
- More input usually means more steps. The question is how much more.
Đếm số bước làm việc
- Chúng ta đo lường một thuật toán bằng số bước nó thực hiện, chứ không phải giây phút.
- Số bước tính theo giây phụ thuộc vào máy tính; việc đếm số bước thì không.
- Dữ liệu đầu vào lớn hơn thường nghĩa là nhiều bước hơn. Câu hỏi là bao nhiêu hơn.
Reasonable vs unreasonable run time
- Some algorithms grow slowly: double the input, do about double the work.
- Some algorithms grow fast: a little more input means a huge jump in work.
- "Reasonable" run time grows slowly enough to finish; "unreasonable" blows up.
Thời gian chạy hợp lý so với không hợp lý
- Một số thuật toán tăng chậm: gấp đôi dữ liệu đầu vào, chỉ làm khoảng gấp đôi công việc.
- Một số thuật toán tăng nhanh: thêm một chút dữ liệu đầu vào dẫn đến sự tăng vọt lớn về công việc.
- Thời gian chạy "hợp lý" tăng đủ chậm để hoàn thành; "không hợp lý" thì bùng nổ.
Input size: 10 20 40
Search a list: 10 20 40 (slow growth - reasonable)
Try all orders: 3,628,800 ... a number with 48 digits (explodes!)
A tiny demo: counting steps
- Below we count the comparisons a linear search makes.
- The count grows in step with the list size — slow, steady growth.
- Try changing the size to see the count follow it.
Một bài minh họa nhỏ: đếm số bước
- Dưới đây chúng ta đếm số phép so sánh mà tìm kiếm tuyến tính thực hiện.
- Số đếm tăng tương ứng với kích thước danh sách — sự tăng trưởng chậm, ổn định.
- Thử thay đổi kích thước để xem số đếm bám theo nó.
def count_steps(n):
steps = 0
data = list(range(n))
target = -1 # not in the list, so we scan everything
for item in data:
steps = steps + 1
if item == target:
break
return steps
print(count_steps(10))
print(count_steps(20))
print(count_steps(40))
When fast is not enough
- Some problems have no known fast algorithm.
- The only methods try a huge number of possibilities — too slow for big input.
- For these, we often accept a good-enough answer instead of the perfect one.
Khi tốc độ nhanh vẫn chưa đủ
- Một số vấn đề không có thuật toán nhanh nào được biết đến.
- Các phương pháp duy nhất thử một số lượng khổng lồ các khả năng — quá chậm đối với dữ liệu đầu vào lớn.
- Đối với những trường hợp này, chúng ta thường chấp nhận một câu trả lời đủ tốt thay vì cái hoàn hảo.
Undecidable problems
- Worse than slow: some problems cannot be solved by any algorithm at all.
- These are called undecidable problems.
- No matter how fast computers get, no program can always give the right answer.
Các vấn đề không thể giải quyết được
- tệ hơn là chậm: một số vấn đề không thể được giải quyết bởi bất kỳ thuật toán nào.
- Những vấn đề này được gọi là các vấn đề không thể quyết định được.
- Dù máy tính có nhanh đến đâu, không có chương trình nào có thể luôn đưa ra đáp án đúng.
Fast : finishes quickly, even for big input
Slow but doable : finishes, but may take a very long time
Undecidable : no algorithm can solve it for every input
Key ideas to remember
- Efficiency is about how work grows with input size.
- Slow-growing algorithms scale to big inputs; fast-growing ones do not.
- Some problems are unreasonable to solve exactly, and some are undecidable.
Ý tưởng quan trọng cần ghi nhớ
- Hiệu suất liên quan đến cách khối lượng công việc tăng theo kích thước dữ liệu đầu vào.
- Các thuật toán tăng chậm có thể mở rộng cho dữ liệu đầu vào lớn; các thuật toán tăng nhanh thì không.
- Một số vấn đề không hợp lý khi giải quyết chính xác, và một số là không thể quyết định được.
Common mistakes
- Big-O describes how the running time GROWS with the input size.
- A reasonable-time algorithm scales; an unreasonable one does not.
Lỗi thường gặp
- Big-O mô tả cách thời gian chạy tăng theo kích thước dữ liệu đầu vào.
- Một thuật toán hợp lý có thể mở rộng; một thuật toán không hợp lý thì không.
Now you try
- Write small functions that count steps to feel how the work grows.
- Compare a single loop, a nested loop, and "try all orders". Press Check answer.
Bây giờ bạn thử
- Viết các hàm nhỏ để đếm số bước nhằm cảm nhận cách khối lượng công việc tăng lên.
- So sánh một vòng lặp đơn, một vòng lặp lồng nhau, và "thử tất cả các thứ tự". Nhấn Kiểm tra câu trả lời.
How algorithms scale · Cách thuật toán mở rộng
As input grows, O(n²) explodes while O(log n) barely moves. · Khi đầu vào tăng lên, O(n²) tăng vọt trong khi O(log n) hầu như không di chuyển.
Write scan_compares(data, target) that returns how many comparisons a linear search makes. Compare each item to target, counting one each time, and stop as soon as you find it. If it is not in the list, you compared every item. Example: scan_compares([5, 8, 2], 8) → 2. · Viết scan_compares(data, target) trả về số lần so sánh mà tìm kiếm tuyến tính thực hiện. So sánh mỗi mục với target, đếm một lần mỗi khi so sánh, và dừng ngay khi bạn tìm thấy nó. Nếu nó không có trong danh sách, bạn đã so sánh mọi mục. Ví dụ: scan_compares([5, 8, 2], 8) → 2.
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.
Write pair_count(n) that uses a loop inside a loop (both over range(n)) and returns how many times the inner step runs. This is n × n. Example: pair_count(3) → 9. This grows much faster than a single loop. · Viết pair_count(n) sử dụng vòng lặp bên trong một vòng lặp khác (cả hai đều lặp qua range(n)) và trả về số lần bước nội bộ được thực hiện. Điều này là n × n. Ví dụ: pair_count(3) → 9. Điều này tăng nhanh hơn nhiều so với một vòng lặp đơn lẻ.
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.
Write count_orderings(n) that returns how many different orders n items can be placed in — that is 1 × 2 × ... × n (n factorial). count_orderings(0) is 1. Example: count_orderings(3) → 6. Notice how fast it explodes: count_orderings(10) is over 3 million. · Viết count_orderings(n) trả về số cách sắp xếp khác nhau của n mục — tức là 1 × 2 × ... × n (n giai thừa). count_orderings(0) là 1. Ví dụ: count_orderings(3) → 6. Hãy chú ý tốc độ tăng trưởng nhanh chóng của nó: count_orderings(10) vượt quá 3 triệu.
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.