Đúng kết quả rồi mới xét nhanh
Một chương trình chạy rất nhanh nhưng trả sai vẫn không đáp ứng bài toán. Ta xét tính đúng theo yêu cầu, sau đó đếm công việc cần làm để so hiệu quả.
Phép toán và độ lớn dữ liệu
Kiểm thử so kết quả thực tế với kết quả dự kiến trên các trường hợp có ý nghĩa: thông thường, ranh giới, rỗng/trùng nếu thuộc phạm vi. Kiểm thử không chứng minh hoàn toàn tính đúng.
Độ phức tạp thời gian mô tả mức tăng công việc theo kích thước n, thường tập trung vào phép toán tích cực. Một lượt qua n phần tử có mức tuyến tính O(n); hai vòng lồng, mỗi vòng n lượt thường O(n²); liên tục chia đôi phạm vi thường O(log n). Các đoạn liên tiếp cộng chi phí, không nhân như vòng lồng. Số giây thực tế còn phụ thuộc máy, dữ liệu và cách cài đặt.
Đếm vòng lặp lồng
```python
n = 4
count = 0
for i in range(n):
for j in range(n):
count += 1
print(count)
```
Mỗi i có 4 lượt j, có 4 giá trị i nên count=16. Với n tổng quát, phép tăng chạy n² lần. Không cộng thành 2n vì hai vòng lồng nhau.
Thử vận dụng
Hai vòng for độc lập, mỗi vòng duyệt n phần tử một lần, tổng số lượt thân vòng là gì?
Nhân n×n phù hợp hai vòng lồng mỗi vòng n lượt.
Đúng: cộng chi phí hai đoạn nối tiếp.
Không có quá trình nhân đôi số trường hợp theo n.
Không có chia đôi phạm vi trong mô tả.
Lời giải
Hai đoạn chạy nối tiếp nên n+n=2n, có mức tăng tuyến tính.
Dữ liệu làm lộ lỗi
Hàm tìm số lớn nhất khởi tạo best=0 rồi chỉ cập nhật khi gặp số lớn hơn best sẽ sai với dãy toàn âm. Dãy [-5,-2,-7] phải cho −2 nhưng hàm trả 0. Nếu chỉ thử số dương, ta có thể bỏ sót lỗi; với dãy không rỗng, khởi tạo bằng phần tử đầu là một cách sửa.
Ví dụ xem cách làm
Đếm số lần tăng s trong: for i in range(4): for j in range(i): s += 1 (hai vòng lồng).
Lời giải
0+1+2+3=6. Vòng trong phụ thuộc i nên không lấy 4×4.
Ví dụ xem cách làm
Một thuật toán vượt qua 20 bộ thử có chứng minh đúng cho mọi đầu vào không?
Lời giải
Không. Những bộ thử ấy chỉ xác nhận các trường hợp đã kiểm. Cần tiếp tục lập luận về thuật toán và phạm vi dữ liệu; số bộ thử tự nó không phải chứng minh.
Những điều cần nhớ
Chọn dữ liệu thử để phát hiện loại lỗi cụ thể. Khi ước lượng, nhìn cấu trúc và số lượt thực tế; không đoán độ phức tạp chỉ từ số dòng mã.
Đang học