Đúng trước, rồi xét tài nguyên
Một chương trình trả kết quả sai dù chạy rất nhanh vẫn chưa giải đúng bài toán. Với chương trình đã đáp ứng yêu cầu, có thể xem nó dùng bao nhiêu **thời gian** và **bộ nhớ** khi dữ liệu tăng. Kích thước đầu vào thường kí hiệu `n`; nếu đầu vào là một dãy thì `n` là số phần tử. Không có một tiêu chí “quan trọng nhất” cho mọi tình huống: ứng dụng xử lí dữ liệu lớn có thể chú trọng thời gian, thiết bị ít RAM có thể chú trọng bộ nhớ. Tính dễ hiểu và dễ bảo trì cũng đáng cân nhắc.
Đếm bước để hiểu khác biệt
Giả sử cần tìm số lớn nhất của dãy số không rỗng. Cách duyệt một lượt xem mỗi phần tử một lần, giữ giá trị lớn nhất hiện có. Một cách khác sắp xếp cả dãy rồi lấy phần tử cuối. Hai cách có thể cùng cho đáp án đúng, nhưng thực hiện công việc khác nhau và yêu cầu bộ nhớ có thể khác tùy cách cài đặt. Muốn so sánh công bằng, cần cùng yêu cầu đầu vào/đầu ra và cùng điều kiện chạy; bài sau sẽ học cách ước lượng số bước khi `n` tăng.
Bài luyện
Hai tiêu chí tài nguyên cơ bản để đánh giá hiệu quả thuật toán là gì?
Đó không phải hai tài nguyên thuật toán chính.
Thời gian và không gian/bộ nhớ là hai tiêu chí chính.
Các yếu tố này giúp đọc mã nhưng không thay hai tài nguyên.
Không phản ánh tài nguyên của thuật toán.
Lời giải
Đánh giá hiệu quả thường xét thời gian chạy và không gian bộ nhớ cần dùng.
Bài luyện
Chương trình A chạy nhanh nhưng trả sai kết quả ở một đầu vào hợp lệ. Nhận xét nào đúng?
Tốc độ không bù được đáp án sai.
Một phản ví dụ hợp lệ cho thấy lỗi.
Bộ nhớ không sửa kết quả sai.
Một ca sai là đủ để cần sửa.
Lời giải
Tính đúng là điều kiện riêng; chương trình nhanh nhưng sai vẫn phải được sửa.
Bài luyện
Nếu đầu vào là một dãy `a`, kích thước `n` thường là gì?
Giá trị phần tử không phải kích thước dãy.
Tổng không cho biết số lượng phần tử.
n = len(a) trong cách xét thông thường của bài.
Biểu thức này không phải quy ước kích thước.
Lời giải
Với dữ liệu đầu vào là dãy, n thường bằng len(a).
Đang học