Tầm quan trọng của giải thuật trong việc xử lý các bài toán.

Để hiểu được tại sao kiến thức về giải thuật và việc hiểu biết về giải thuật lại quan trọng chúng ta cần định nghĩa chính xác xem giải thuật là gì? Một định nghĩa về giải thuật được viết trong cuốn " Introduction to Algorithms " khá phổ biến như sau: Một giải thuật là thủ tục hay trình tự thực hiện các công việc của máy tính được định nghĩa rõ ràng, trong đó nó nhận vào giá trị hoặc một tập giá trị (gọi là input) và sinh ra giá trị hoặc một tập giá trị (gọi là output). Nói cách khác giải thuật như là tấm bản đồ, chỉ dẫn để hoàn thành công việc.Ví dụ một đoạn code tính toán các giá trị của dãy số fibonaci là một cài đặt cho một giải thuật cụ thể, mặc dù giải thuật đó đơn giản chỉ là cộng 2 số liền nhau . Một số giải thuật như ví dụ trên tính toán số tiếp theo của dãy fibonaci, có thể dễ dàng nhận biết và thậm chí được cài đặt một cách bẩm sinh trong hệ thống tư duy logic và khả năng giải quyết vấn đề của chúng ta.Tuy nhiên với hầu hết chúng ta những giải thuật phức tạp chính là những "best studied" để từ đó chúng ta có thể sử dụng một phần của chúng để xây dựng những giải thuật tốt cho những vấn đề khác trong tương lai.Trên thực tế con người sử dụng những giải thuật rất phức tạp để làm những việc đơn giản như check email, nghe nhạc ... Bài viết này giới thiệu một số ý tưởng cơ bản nhất về phân tích giải thuật và áp dụng chúng vào những ví dụ minh họa để làm rõ hơn tầm quan trọng của giải thuật.

Một trong những vấn đề qua trọng nhất của giải thuật đó là: giải thuật nhanh tới mức nào? Thông thường các giải thuật không tốn nhiều thời gian để xử lý một vấn đề nào đó, tuy nhiên trong trường hợp giải thuật quá chậm thì chúng ta cần xem xét lại giải thuật đó. Tốc độ chính xác của giải thuật phụ thuộc vào việc nó chạy trên nền tảng nào cũng như việc giải thuật đó được cài đặt tốt tới mức nào, một yếu tố nữa thường được các nhà khoa học máy tính nhắc đến là độ lớn của input. Ví dụ một bài toán có độ lớn input là n số tự nhiên, một giải thuật có runtime tỷ lệ thuận với N2 (được gọi là O(N2)) thì khi chạy cài đặt của giải thuật này trên máy tính với độ lớn của input là N thì máy tính sẽ mất C*N2 giây để đưa ra được kết quả. Với C là một hằng số không phụ thuộc vào N. Tuy nhiên độ nhanh của thuật toán không chỉ phụ thuộc vào size của input mà còn phụ thuộc nhiều yếu tố khác, ví dụ một giải thuật sắp xếp sẽ chạy nhanh hơn nếu đầu vào của nó đã được sắp xếp một phần theo thứ tự hơn khi chạy giải thuật đó với đầu vào với thứ tự ngẫu nhiên. Yếu tố này tạo ra "worst-case runtime", "average-case runtime" mà chúng ta thường nghe. worst-case runtime: là thời gian chạy của giải thuật trong trường hợp giải thuật tốn nhiều thời gian nhất với bộ input đầu vào. average-case runtime: là thời gian chạy trung bình của giải thuật đối với tất cả các bộ input. Thông thường việc tính toán worst-case runtime dễ dàng hơn là average-case runtime nên nó thường được dùng như một tiêu chí phổ biến trong việc đánh giá giải thuật. Rất khó để chạy giải thuật cho tất cả các trường hợp input, do đó người ta thường dùng một số mẹo để tính một cách gần chính xác average-case runtime cho các giải thuật. Dưới đây là một số nguồn tham khảo về average-case runtime:

Các giải thuật sắp xếp là những ví dụ điển hình về thuật toán và thường được sử dụng. Cách đơn giản nhất để sắp xếp các phần tử trong một nhóm là lấy phần tử nhỏ nhất khỏi nhóm và đưa lên đầu tiên, tuy nhiên độ phức tạp của giải thuật này là O(N^2) có nghĩa là thời gian chạy của giải thuật sẽ tỷ lệ thuận với bình phương của độ lớn input. Nếu như thực hiện sắp xếp 1tỷ phần tử thì cần thực hiện 10^18 phép tính. Một pc thông thường có thể chạy khoảng 10^9 phép tính mỗi giây và nếu thực hiện sắp xếp theo cách ở trên thì phải mất đến hàng năm mới thực hiện xong. Thật may là có những giải thuật khác tốt hơn (quicksort, heapsort, mergesort..) những giải thuật này đã được phát hiện ra từ nhiều năm trước, phần lớn giải thuật trong số này có độ phức tạp O(N * Log(N)). Điều này sẽ giảm thiểu một lượng lớn các phép tính cần thực hiện và giúp thời gian xử lý bài toán nhanh hơn nhiều dù chạy trên máy tính cùi bắp hơn. Thay vì thực hiện 10^18 phép tính, giải thuật này chỉ thực hiện 10^10 phép tính, có nghĩa là nhanh hơn 100 triệu lần.

Bài toán tìm đường đi ngắn nhất đã được nghiên cứu trong nhiều năm và có nhiều ứng dụng. Tuy nhiên hãy cứ nghĩ đơn giản là bạn muốn tìm đường đi từ điểm A đến điểm B thông qua vài con đường và các ngã tư. Có khá nhiều giải thuật xử lý bài toán này với những ưu điểm cũng như đánh đổi khác nhau để có được ưu điểm đó. Trước khi tìm hiểu sâu về cách giải quyết thì chúng ta hãy thử tính xem một giải thuật thông thường sẽ mất bao lâu nếu nó tính toán tất cả các khả năng đường đi. Nếu giải thuật cân tính toán hết các khả năng đi từ A đến B (không tính đi vòng tròn) thì sẽ mất nhiều thời gian hơn cả đời người