Độ phức tạp thuật toán

Bách khoa toàn thư mở Wikipedia

[sửa] Đặt vấn đề

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.

[sửa] Định nghĩa

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. Bạn có thể góp sức viết bổ sung cho bài được hoàn thiện hơn. Xem phần trợ giúp để biết thêm về cách sửa đổi bài.