Algorithmic efficiency
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.
Đế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.
Thời gian chạy hợp lý so với không hợp lý
- Thời gian hợp lý có nghĩa là số bước tăng theo hàm đa thức, hoặc chậm hơn: hằng số, tuyến tính, bậc hai hoặc bậc ba.
- Một vòng lặp đơn là tuyến tính. Một vòng lặp nằm trong một vòng lặp khác là bậc hai (n × n). Bậc hai tăng nhanh hơn tuyến tính, nhưng vẫn thuộc loại thời gian hợp lý.
- Thời gian không hợp lý có nghĩa là tăng trưởng cấp số mũ hoặc giai thừa. Một chút tăng thêm đầu vào sẽ khiến khối lượng công việc bùng nổ.
Input size: 10 20 40
Search a list: 10 20 40 (linear - reasonable)
Nested loops: 100 400 1,600 (square - still reasonable)
Try all orders: 3,628,800 ... 48 digits (factorial - unreasonable)
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))
Khi tốc độ nhanh vẫn chưa đủ
- Một số bài toán không có thuật toán nào giải được trong thời gian hợp lý.
- Một phương pháp chính xác có thể thử mọi thứ tự. Đó là sự tăng trưởng giai thừa, do đó không hợp lý với đầu vào lớn.
- Một thuật toán tham chiếu (heuristic) là một cách rút gọn có thể đưa ra câu trả lời đủ tốt. Nó không đảm bảo là câu trả lời tốt nhất. Bạn không cần phải ghi nhớ một thuật toán tham chiếu cụ thể nào đó.
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.
Reasonable : constant, linear, square or cube growth
Unreasonable : exponential or factorial growth
Undecidable : no algorithm can solve it for every input
Ý tưởng quan trọng cần ghi nhớ
- Hiệu quả liên quan đến việc số bước tăng lên theo kích thước đầu vào như thế nào, chứ không phải bao nhiêu giây một máy tính mất để thực hiện.
- Sự tăng trưởng đa thức hoặc thấp hơn là thời gian hợp lý. Một vòng lặp lồng nhau (n × n) vẫn còn hợp lý.
- Sự tăng trưởng mũ hoặc giai thừa là không hợp lý. Một số bài toán cũng không thể quyết định được.
Lỗi thường gặp
- Gọi một vòng lặp lồng nhau là không hợp lý. Sự tăng trưởng bậc hai và bậc ba vẫn nằm trong khoảng thời gian hợp lý.
- Sử dụng ký hiệu Big-O chính thức làm quy tắc thi. Big-O không được kiểm tra. Đường phân chia là đa thức hoặc thấp hơn, so với mũ hoặc giai thừa.
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ự". Vòng lặp lồng nhau vẫn nằm trong khoảng thời gian hợp lý. Nhấn Kiểm tra câu trả lời.
How algorithms scale
Square growth rises faster than a straight line, and it is still reasonable time. Factorial growth is unreasonable.
Độ khó 3/5 · 200 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
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.
Nhấn Chạy để xem kết quả ở đây.
Độ khó 3/5 · 200 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
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.
Nhấn Chạy để xem kết quả ở đây.
Độ khó 3/5 · 200 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
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) là (is) 1. Example: count_orderings(3) → 6. Notice how fast it explodes: count_orderings(10) is over 3 million.
Nhấn Chạy để xem kết quả ở đây.