Giữ bậc tăng, bỏ chi tiết cố định
Nếu số thao tác có dạng `T(n) = n + 3`, khi `n` lớn, phần `n` quyết định tốc độ tăng; ta viết `T(n) = O(n)`. Với `T(n) = n² + 3`, ta viết `O(n²)`. Kí hiệu **O lớn** nói rằng sau một ngưỡng nào đó, `T(n)` không vượt quá một hằng số nhân với hàm được nêu. Đây là **chặn trên theo bậc**, không phải phương trình cho số giây hay lời hứa hai thuật toán có thời gian chạy bằng nhau.
Cụ thể, `n + 3 ≤ 2n` khi `n ≥ 3`. Vì vậy `c = 2` và ngưỡng `n₀ = 3` là một chứng cứ cho `n + 3 = O(n)`. Tương tự, `n² + 3 ≤ 2n²` khi `n ≥ 2`.
Ba dạng cơ bản
Một thao tác độc lập với độ dài dãy là `O(1)`. Duyệt một dãy `n` phần tử một lượt là `O(n)`. Hai vòng, mỗi vòng `n` lượt và lồng nhau, là `O(n²)` theo mô hình thao tác đơn giản. Khi `n` tăng từ 10 lên 100, số lượt một vòng tăng từ 10 lên 100, còn số lượt hai vòng tăng từ 100 lên 10 000. Đây là cách so tốc độ tăng; không suy ra hai chương trình có cùng kết quả hay số giây cụ thể.
Bài luyện
Với `T(n) = n² + 3`, chặn trên nào thể hiện bậc chính theo ví dụ của bài?
T(n) tăng theo n.
n² tăng nhanh hơn n khi n lớn.
Hạng n² quyết định bậc tăng.
Logarit tăng chậm hơn n².
Lời giải
Khi n lớn, hạng n² chi phối; n² + 3 ≤ 2n² với n ≥ 2, nên T(n) = O(n²).
Bài luyện
Phát biểu nào đúng về `T(n) = O(n)`?
O lớn không cho số giây.
Đây là ý nghĩa chặn trên tiệm cận.
Không đòi bằng nhau.
Hằng số và dữ liệu nhỏ vẫn ảnh hưởng thời gian thực.
Lời giải
O(n) cho một chặn trên dạng c·n khi n đủ lớn; nó không xác định chính xác thời gian chạy.
Bài luyện
Khi `n` tăng từ 10 lên 100, `n²` tăng từ bao nhiêu lên bao nhiêu?
Đây là giá trị n.
100² không bằng 1000.
10²=100 và 100²=10 000.
10² không bằng 1000.
Lời giải
Bình phương 10 được 100; bình phương 100 được 10 000.
Đang học