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 có thể dùng nhiều loại phép toán khác nhau. Sau đây ta xét một ví dụ đơn giản.

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

Phương pháp 1: Theo cách sắp xếp các số thứ tự, bắt đầu so sánh số a1 với n - 1 số còn lại, nếu phát hiện thấy có một số lớn hơn a1 thì rõ ràng a1 không phải là số lớn nhất. Lại lấy số a2 so với n - 1 số còn lại....cứ thế tiến hành cuối cùng sẽ tìm được số lớn nhất.

Phương pháp 2: Trước hết đem a1 so với a2, nếu a1 > a2, ta lại đem so a1 với a3, không cần phải so sánh a2 với a3. Khi so a1 với a2 hoặc a2 so với a3, ta tìm được số lớn nhất, trong ba số đem so với a4. Trong khi so sánh hai số ắt tìm được một số lớn hơn trong hai số đó và cuối cùng sẽ tìm được số lớn nhất trong các số đã đem so. Vì vậy chỉ cần n - 1 lần so là có thể tìm được số lớn nhất trong các số đã xét.

Trong hai phương pháp thì phương pháp nào hợp lí hơn? Rõ ràng là phương pháp hai. Với phương pháp hai, số lần tiến hành so sánh các số ít hơn phương pháp một. Với số n lớn thì thực hiện theo phương pháp 2 sẽ thu được kết quả nhanh hơn. Do vậy phép toán có thể tốt có thể xấu. Do đó khi thiết kế các phép toán để giải quyết một vấn đề cụ thể, người ta hi vọng tìm được một phép toán thực hiện bài toán nhanh nhất. Thế làm thế nào để đánh giá được phép toán là tốt hay xấu?

Một trong các tiêu chuẩn để đánh giá phép toán là tốt hay xấu là khi máy tính chấp hành phép toán để giải quyết một vấn đề nào đó thì tiêu phí thời gian dài hay ngắn. Trong ví dụ nêu trên, với số n rất lớn hiển nhiên dùng phương pháp 2 thời gian sử dụng để giải bài toán sẽ ngắn hơn khi dùng phương pháp 1. Nói chung khi chọn phép toán để giải quyết một vấn đề nào đó, căn cứ đầu tiên phải cân nhắc là quy mô. Ở ví dụ nêu trên, quy mô của bài toán là n. Thời gian sử dụng phép toán để giải bài toán được quyết định do n. Với phương pháp 2, thời gian tiêu phí được đánh giá bằng n - 1.

Thông thường mục tiêu tìm kiếm là chọn các phép toán có nhiều số hạng. Với các phép toán nhiều số hạng, thời gian tiêu phí cho quy mô n là một hạng thức nhiều số hạng. So với phép toán theo chỉ số (thời gian tiêu chí cho quy mô được biểu diễn theo chỉ số) thì phép toán theo hạng thức nhiều số hạng tiết kiệm thời gian hơn, trong đó n biểu diễn quy mô của bài toán:

Từ đó có thể thấy khi n càng lớn thì tiêu tốn thời gian của phép toán theo chỉ số càng nhiều. Cho dù tốc độ của máy tính rất lớn (ví dụ cỡ một tỉ phép tính/giây) thì hàm chỉ số đã tăng với tốc độ kinh người khi n tăng và máy tính sẽ không đảm nhiệm nổi. Giả sử chúng ta sử dụng máy tính có tốc độ 100.000 phép tính/giây thì với phép toán 230 cần thời gian làm việc 104 giây tức khoảng 3 giờ. Với thời gian như vậy còn có thể chấp nhận được. Nhưng với phép toán hao phí thời gian cỡ 2150, 21000 thì sẽ ra sao? Rõ ràng là các máy tính sẽ bó tay.

Do máy tính không thể giải quyết các vấn đề có cơ sở dữ liệu quá lớn, nên khi giải quyết các bài toán phức tạp cần tìm các phép toán (hay thuật toán) mà máy tính có thể có khả năng tiếp thu được. Đó là lí do tại sao ta cần tìm các phép toán (thuật toán) nhiều số hạng.