Thời gian làm việc của một máy tính khi chạy một thuật toán không chỉ phụ thuộc vào thuật toán mà còn phụ thuộc vào máy tính. Vì vậy để đánh giá hiệu quả của một thuật toán ta sẽ số các phép tính phải thực hiện khi thực hiện thuật toán. Khi tiến hành một thuật toán thì số các phép tính cần làm còn phụ thuộc vào cỡ của bài toán, tức là độ lớn của đầu vào. Vì thế độ phức tạp tính toán là một hàm phụ thuộc đầu vào. Tuy nhiên trong những ứng dụng thực tiễn, chúng ta không cần biết chính xác hàm này mà chỉ cần biết một ước lượng đủ tốt của chúng.
Để ước lượng độ phức tạp của một thuật toán ta dùng khái niệm bậc O-lớn.
Giả sử f(n), g(n) là hai hàm xác định trên tập hợp các số nguyên dương. Ta nói f(n) có bậc O-lớn của g(n), và viết f(n) = O(g(n)), nếu tồn tại một số C > 0 sao cho với n đủ lớn, các hàm f,g đều dương và f(n) < C.g(n)
 |
Bài này còn sơ khai. Mời bạn góp sức viết thêm để bài được hoàn thiện hơn. Xem phần trợ giúp về cách sửa bài. |
