Chọn một thao tác để đếm
Khi phân tích, có thể coi phép cộng hoặc so sánh đơn giản là một **đơn vị thao tác**. Cách đếm này giúp nhìn ra số bước thay đổi ra sao khi kích thước đầu vào `n` tăng. Nó không cho biết chính xác chương trình chạy bao nhiêu giây, vì từng thao tác và môi trường máy có thể khác nhau. Thao tác chi phối số lần thực hiện thường được gọi là **phép toán tích cực**; một chương trình không nhất thiết chỉ có đúng một phép toán như vậy.
Với `n` không âm, đoạn sau tăng `c` đúng `n` lần:
```python
def dem_mot_vong(n):
c = 0
for k in range(n):
c += 1
return c
```
Phép cộng `c += 1` được thực hiện `n` lần; khởi tạo và trả kết quả chỉ thêm số thao tác không phụ thuộc `n`.
Hai vòng lồng nhau nhân số lượt
Đặt một vòng `n` lượt vào trong một vòng `n` lượt:
```python
def dem_hai_vong(n):
c = 0
for i in range(n):
for j in range(n):
c += 1
return c
```
Mỗi lượt vòng ngoài chạy đủ `n` lượt vòng trong, nên phép cộng xảy ra `n × n = n²` lần. Với `n = 4`, hai hàm trả lần lượt 4 và 16. Chúng **không giải cùng một bài toán**: kết quả đếm cũng khác. Ở đây chúng chỉ minh họa cách số thao tác tăng.
Bài luyện
Với `n = 5`, `dem_hai_vong(n)` thực hiện phép `c += 1` bao nhiêu lần?
Đây là số lượt một vòng.
Hai vòng lồng nhau không cộng số lượt theo cách này.
5 lượt ngoài, mỗi lượt 5 lượt trong: 25.
Khởi tạo không phải phép c += 1.
Lời giải
Mỗi trong 5 lượt ngoài có 5 lượt trong; 5 × 5 = 25 phép cộng.
Bài luyện
Vì sao không lấy “mỗi thao tác bằng một đơn vị” làm số giây chạy chính xác?
Thời gian thao tác và môi trường thực tế khác nhau.
Python có vòng lặp for và while.
n là kích thước thay đổi được.
Tốc độ máy không giống nhau.
Lời giải
Đơn vị thao tác là quy ước phân tích; không đại diện cho số giây cố định trên mọi máy.
Bài luyện
Với hai hàm trong bài, nhận xét nào đúng?
Ví dụ n=4 cho 4 và 16.
Đếm theo số lượt cho đúng hai kết quả này.
Một vòng chỉ có n lượt.
Không có điều kiện kiểm chẵn.
Lời giải
Với n không âm, một vòng tăng n lần; hai vòng lồng nhau tăng n × n lần.
Đang học