Vì sao ta cần tìm phép toán nhiều số hạng?

Thông thường, khi nói đến phép toán là nói đến phương pháp giải toán. Khi cần giải một bài toán, ta có thể dùng nhiều loại phép toán khác nhau. Hãy xét một ví dụ đơn giản.

Có n số a1, a2, ..., an và cần tìm số lớn nhất trong các số đó. Có thể làm theo hai cách.

Phương pháp thứ nhất: theo thứ tự các số, bắt đầu so sánh a1 với n - 1 số còn lại. Nếu phát hiện có số lớn hơn a1 thì rõ ràng a1 không phải số lớn nhất. Sau đó lại lấy a2 so với n - 1 số còn lại, rồi tiếp tục như vậy cho đến khi tìm được số lớn nhất.

Phương pháp thứ hai: trước hết đem a1 so với a2. Nếu a1 > a2, ta lại đem a1 so với a3; khi đó không cần so sánh a2 với a3 nữa. Sau mỗi lần so sánh hai số, ta giữ lại số lớn hơn rồi đem so với số tiếp theo. Cứ như vậy, cuối cùng sẽ tìm được số lớn nhất trong tất cả các số đã xét. Theo cách này, chỉ cần n - 1 lần so sánh là có thể tìm được số lớn nhất.

Trong hai phương pháp trên, phương pháp nào hợp lý hơn? Rõ ràng là phương pháp thứ hai, vì số lần so sánh ít hơn phương pháp thứ nhất. Khi n rất lớn, dùng phương pháp thứ hai sẽ cho kết quả nhanh hơn nhiều. Điều đó cho thấy phép toán có thể tốt hoặc chưa tốt. Khi thiết kế phép toán để giải quyết một vấn đề cụ thể, người ta luôn hy vọng tìm được cách thực hiện nhanh nhất. Vậy làm thế nào để đánh giá một phép toán tốt hay xấu?

Một trong những tiêu chuẩn đánh giá phép toán là thời gian máy tính cần để thực hiện phép toán đó. Trong ví dụ trên, khi n rất lớn, phương pháp thứ hai hiển nhiên tốn ít thời gian hơn phương pháp thứ nhất. Nói chung, khi chọn phép toán để giải một vấn đề, điều đầu tiên cần cân nhắc là quy mô bài toán. Ở ví dụ này, quy mô bài toán là n. Thời gian thực hiện phép toán phụ thuộc vào n. Với phương pháp thứ hai, số lần so sánh là n - 1.

Thông thường, người ta muốn tìm các thuật toán có thời gian đa thức. Với thuật toán đa thức, thời gian tiêu phí theo quy mô n được biểu diễn bằng một đa thức. So với thuật toán theo hàm mũ, tức thời gian tăng theo dạng lũy thừa, thuật toán đa thức tiết kiệm thời gian hơn rất nhiều.

Khi n càng lớn, thời gian tiêu tốn của thuật toán hàm mũ càng tăng khủng khiếp. Dù tốc độ máy tính rất cao, chẳng hạn một tỉ phép tính mỗi giây, hàm mũ vẫn có thể tăng nhanh đến mức máy tính không đảm nhiệm nổi. Giả sử dùng máy tính có tốc độ 100.000 phép tính mỗi giây, một phép toán cỡ 2³⁰ đã cần khoảng 10⁴ giây, tức gần 3 giờ. Nếu gặp phép toán cỡ 2¹⁵⁰ hoặc 2¹⁰⁰⁰ thì máy tính gần như bó tay.

Vì máy tính không thể xử lý hiệu quả những vấn đề có dữ liệu quá lớn bằng các thuật toán tăng quá nhanh, nên khi giải các bài toán phức tạp, ta cần tìm những thuật toán mà máy tính có thể tiếp nhận được. Đó là lý do phải tìm các thuật toán nhiều số hạng, hay thuật toán đa thức.