Vài Nét Về Thuật Toán - Devera Academy

Trên con đường trở thành một lập trình viên, một điều không thể bỏ qua đo là gây dựng cho bản thân một kho "công cụ" phong phú để sử dụng linh hoạt trong nhiều mục đích khác nhau. Các công cụ này bao gồm ngôn ngữ lập trình, trình soạn thảo, các package,... và thuật toán - một công cụ không kém phần quan trọng. Hiểu được một vài thuật toán thông dụng, các cuộc phỏng vấn về kỹ thuật khi đi xin việc đối với bạn sẽ dễ dàng hơn.

Sơ lược về thuật toán

Thực ra mà nói, thuật toán cũng không phải là một khái niệm quá sức khó hiểu. Các thuật toán hiểu một cách đơn giản là các giải pháp đã được xác định rõ ràng từng bước dùng xử lý các vấn đề. Ví dụ như một bài tập trong các lớp học về khoa học máy tính,  học sinh được yêu cầu trình bày cách làm bánh mì kẹp bơ đậu phộng và mứt trái cây. Quá trình làm được xem là một thuật toán, trong tài liệu hướng dẫn của MIT cung cấp chi tiết về thuật toán này như sau:

1. Lấy một lát bánh mì

2. Mở lọ bơ đậu phộng bằng cách vặn nắp ngược chiều kim đồng hồ

3. Lấy một con dao bằng tay cầm

4. Cắm dao vào lọ bơ đậu phộng

5. Rút con dao ra khỏi lọ bơ đậu phộng và di chuyển qua lại nó trên lát bánh mì

6. Lấy một lát bánh mì thứ hai

7. Lặp lại bước 2-5 với lát bánh mì thứ hai và lọ mứt trái cây.

8. Úp hai lát bánh mì vào nhau sao cho bơ đậu phộng và mứt chạm vào nhau

Như bạn có thể thấy, mỗi bước vô cùng rõ ràng, giảm thiểu tối đa các sai sót. Điều này là do các thuật toán thường được máy tính diễn giải nên một các khách quan - nó chả hiểu gì cả. Ví dụ như bạn đưa cho máy tính một danh sách gồm 7 thứ và yêu cầu mục thứ 8. Một người đủ thông minh sẽ trả lời rằng "Chỉ có bảy điều trong danh sách, vì vậy tôi không thể đưa cho bạn điều thứ tám." Tuy nhiên, một máy tính thì có thể nó sẽ bị hỏng.

Thế nhưng về mặt tích cực hơn đó là máy tính rất nhanh, chúng chạy các thuật toán phức tạp thực sự hiệu quả hơn những gì mà con người có thể làm được. Một máy tính có thể sắp xếp danh sách 100 thứ trong một vài tích tắc, miễn là nó được hướng dẫn rõ ràng chi tiết cách thực hiện.

Có những loại thuật toán nào?

Máy tính được yêu cầu thực hiện nhiều tác vụ khác nhau và theo như dự kiến ​​máy tính cần phải thực hiện các tác vụ một cách nhanh chóng. Kể từ trước khi chiếc máy tính đầu tiên được phát minh, các học giả đã đi vào việc nghiên cứu các thuật toán: họ thiết kế những cách mới và hiệu quả để giải quyết một vấn đề. Dưới đây là hai trong số các mô hình thuật toán nổi tiếng:

The brute force approach - Thuật toán vét cạn

Hãy tưởng tượng bạn đang tìm từ “mật mã” trong từ điển. Người thông minh chỉ cần lật đến phần chứa các từ bắt đầu bằng chữ m, và lật đi từ đó. Hiệu quả mà đúng không? Nhưng mà máy tính thì không có các định nghĩa về ngôn ngữ. Do đó, người ta sẽ đưa ra đề xuất về việc sử dụng phương pháp vét cạn để giải quyết vấn đề này.

Cách tiếp cận của thuật toán này đòi hỏi việc xem xét từng từ trên mỗi trang, cho đến khi từ "mật mã" xuất hiện. Đây là một đòi hỏi cũng không quá hiệu quả. Trên thực tế, chúng ta có thể nói rằng, nếu có n từ trong từ điển trước từ "mật mã", chúng ta sẽ phải thực hiện n phép toán (phép toán kiểm tra xem chúng ta có tìm được từ "mật mã" hay không) trước khi tìm được từ chính xác.

Hãy tưởng tượng tình huống xấu nhất. Giả sử bạn muốn tìm kiếm từ “zzzzzz”. Rõ ràng, từ này không tồn tại, nhưng nếu bạn muốn kiểm tra lại thì sao? Sử dụng thuật toán vét cạn, bạn sẽ lật qua từng trang, xem từng từ, cho đến khi bạn đến từ cuối cùng trong từ điển (Zyzzyva) để chắc chắn rằng “zzzzzz” không phải là một từ. Tương tự như ví dụ trước, điều này sẽ yêu cầu n thao tác nếu chúng ta có n từ trong từ điển. Thế nên, cần phải có một cách hiệu quả hơn để giải quyết vấn đề này.

Divide and conquer - Chia để trị

Bây giờ, giả sử rằng từ điển bạn đang xem được sắp xếp theo thứ tự giống như hầu hết các từ điển. Điều đó nghĩa là bạn có thể chia từ điển thành nhiều phần và xác định xem các từ trong mỗi phần xuất hiện trước hay sau “zzzzzz” theo thứ tự bảng chữ cái.

Quy trình làm việc sẽ giống như thế này:

1. Tìm ra vị trí chính giữa từ điển

2. Xác định xem "zzzzzz" có ở vị trí giữa đó hay không. Nếu có, công việc của chúng ta đã hoàn thành

3. Nếu không, hãy xác định xem "zzzzzz" đứng trước hay sau vị trí trung tâm từ điển theo thứ tự bảng chữ cái

4. Nếu "zzzzzz" đứng trước, hãy lặp lại các bước này với nửa đầu của từ điển. Nếu không, hãy lặp lại các bước này với nửa sau của từ điển.

Cuối cùng, từ điển sẽ được chia nhỏ ra nhiều lần đến nỗi bạn sẽ chỉ còn lại một hoặc hai từ. Trong cả hai trường hợp đó, việc xác định xem có bất kỳ từ nào còn lại là “zzzzzz” hay không là rất dễ dàng. Không giống như cách tiếp cận theo hướng vét cạn.

Cách tiếp cận theo hướng phân chia khối lượng công việc thành các phần nhỏ hơn và nhỏ hơn chính là chia để trị. Mô hình thuật toán này sử dụng đệ quy, nó sẽ xử lý vấn đề bên trong một vấn đề là phiên bản đơn giản hơn của chính nó. Trong trường hợp này, vấn đề là tìm kiếm “zzzzzz” trong toàn bộ từ điển. “Phiên bản đơn giản hơn” là chúng ta sẽ tìm kiếm “zzzzzz” trong một phần nhỏ hơn của từ điển.

Giải pháp này hiệu quả hơn bao nhiêu? Để xác định điều này, chúng ta cần tính xem chúng ta đã thực hiện bao nhiêu phép toán. Để đơn giản, các bước từ 1 đến 4 trong quy trình làm việc nêu trên được tính là một thao tác. Ở mỗi bước của toàn bộ quá trình chúng ta thực hiện một thao tác duy nhất. Thế thì chúng ta cần thực hiện bao nhiêu bước? Có thể thấy rằng, chúng ta đang tìm “zzzzzz” bằng cách chia đôi kích thước của từ điển. Do đó, nếu từ điển đầy đủ chứa n từ, số lượng từ bị bỏ qua ở mỗi bước là:

n/2 -> n/4 -> n/8 -> n/16 -> n/32 -> .... -> 1

Với một chút phép toán, cuối cùng chúng ta sẽ tính ra rằng không cần tới n phép toán trong trường hợp xấu nhất, chúng ta chỉ cần đến log n. Vì vậy, nếu từ điển chứa 1.000.000 từ, cách tiếp cận "brute force" sẽ yêu cầu 1.000.000 thao tác trong trường hợp xấu nhất, trong đó "divide and conque" chỉ yêu cầu khoảng 20.

Lưu ý rằng log, trong trường hợp này là log cơ số 2.

Tại sao chỉ quan tâm đến trường hợp xấu nhất (worst case)?

Đề cập quá nhiều về tình huống xấu nhất, các nhà khoa học máy tính có vẻ giống như một nhóm người bi quan quá thể. Thế nhưng, điều này là rất là thực tế.

Lo lắng về trường hợp xấu nhất với hy vọng giảm thiểu những tác động xấu (hoặc xác suất gặp phải) của trường hợp xấu nhất. Các tác động xấu có thể bao gồm bất cứ điều gì như  tiêu thụ quá nhiều bộ nhớ, thời gian chạy quá lâu hoặc có khả năng làm ngưng hoặc trì trệ các hoạt động.

Có một ký hiệu nhất định cho việc phân tích thời gian chạy trong trường hợp xấu nhất - Nó được gọi là Big O (Độ phức tạp thuật toán). Đọc bài viết này, bạn đã biết một chút về độ phức tạp của hai thuật toán tìm kiếm phổ biến:

Một cái tên khác của chiến lược tìm kiếm vét cạn là Sqequential Search (tìm kiếm tuần tự). Trong trường hợp xấu nhất, thuật toán này sẽ yêu cầu n thao tác. Do đó, hiệu suất O lớn của thuật toán này là O(n)

Một cái tên khác của chiến lược chia để trị là Binary Search (tìm kiếm nhị phân). Vì nó cần log n thao tác trong trường hợp xấu nhất nên hiệu suất Big O sẽ là O(log n)

Bây giờ bạn đã biết hai phương pháp tìm kiếm thông qua ví dụ về từ điển và cả cách đo lường, mô tả hiệu quả của các thuật toán đó. Cảm ơn bạn đã dành thời gian đọc bài viết nhé!

Tác giả: Evan WiremanDịch bởi Devera Academy