Tản mạn về sự quan trọng của thuật toán trong lập trình

Thuật toán quan trọng nhưng có cần học sâu về nó?

Bước đầu tiên hướng tới một sự hiểu biết về lý do tại sao việc nghiên cứu và hiểu biết các thuật toán rất quan trọng là xác định chính xác những gì chúng ta muốn bằng một thuật toán (Cần học sâu về thuật toán hay không còn phụ thuộc vào yếu tố khác). Theo các thuật toán phổ biến (Second Edition của Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein)...

"Một thuật toán là quy trình tính toán nào được xác định rõ ràng cũng có một số giá trị nào đó, như tạo ra các giá trị đầu vào, hoặc thiết lập các giá trị đầu ra." 

Nói cách khác, các thuật toán giống như các bản đồ để hoàn thành một nhiệm vụ được xác định rõ ràng. Vì vậy, một đoạn mã tính các thuật ngữ của dãy Fibonacci là một sự thực hiện của một thuật toán cụ thể. Ngay cả một chức năng đơn giản để thêm hai con số là một thuật toán trong một ý nghĩa, mặc dù một một đơn giản.

Một số thuật toán, giống như những phép tính của dãy Fibonacci, trực quan và có thể được bẩm sinh gắn vào các kỹ năng giải quyết vấn đề và suy nghĩ hợp lý của chúng ta. Tuy nhiên, đối với hầu hết chúng ta, các thuật toán phức tạp được nghiên cứu tốt nhất nên chúng ta có thể sử dụng chúng làm các khối xây dựng để giải quyết vấn đề logic hiệu quả hơn trong tương lai. Trên thực tế, bạn có thể ngạc nhiên khi biết được có bao nhiêu thuật toán phức tạp mà mọi người sử dụng hàng ngày khi họ kiểm tra e-mail hoặc nghe nhạc trên máy tính của họ. Bài viết này sẽ giới thiệu một số ý tưởng cơ bản liên quan đến phân tích các thuật toán, và sau đó đưa chúng vào thực tiễn với một vài ví dụ minh hoạ cho thấy tại sao biết về thuật toán rất quan trọng.

Phân tích Thời gian chạy

Một trong những khía cạnh quan trọng nhất của một thuật toán là nó nhanh như thế nào. Một thuật toán thường dễ dàng đi đến để giải quyết vấn đề, nhưng nếu thuật toán quá lại chậm. Vì tốc độ chính xác của một thuật toán phụ thuộc vào nơi mà thuật toán được chạy, cũng như các chi tiết chính xác của việc thực hiện nó, các nhà khoa học máy tính thường nói về thời gian chạy liên quan đến kích thước của đầu vào. Ví dụ, nếu đầu vào bao gồm N số nguyên, một thuật toán có thể có thời gian chạy tỷ lệ thuận với N2, được biểu diễn là O (N2). Điều này có nghĩa là nếu bạn chạy một sự thực thi của thuật toán trên máy tính của bạn với một đầu vào của kích thước N, nó sẽ mất C * N2 giây, trong đó C là một số không đổi mà không thay đổi với kích thước của đầu vào.

Tuy nhiên, thời gian thực hiện của nhiều thuật toán phức tạp có thể thay đổi do các yếu tố khác với kích thước của đầu vào. Ví dụ, một thuật toán sắp xếp có thể chạy nhanh hơn nhiều khi đưa ra một tập các số nguyên đã được sắp xếp tốt hơn nó khi đưa ra cùng một tập các số nguyên theo thứ tự ngẫu nhiên. Do đó, bạn thường nghe mọi người nói về thời gian chạy tệ nhất, hoặc thời gian chạy trung bình. Trường hợp tệ nhất là trong thời gian bao lâu để các thuật toán chạy thành công nếu cho input là các vấn đề khó hiểu nhất. Thời gian chạy trung bình là trung bình khoảng thời gian để thuật toán chạy nếu nó được đưa tất cả các input có thể. Trong hai trường hợp, trường hợp tệ nhất thường dễ giải thích hơn, và do đó được sử dụng thường xuyên hơn làm điểm chuẩn cho một thuật toán nhất định. Quá trình xác định thời gian chạy tệ nhất và thời gian chạy trung bình cho một thuật toán nhất định có thể rất phức tạp vì thường không thể chạy một thuật toán trên tất cả các input có thể. Có rất nhiều tài nguyên trực tuyến tốt có thể giúp bạn ước tính các giá trị này.

Phân loại

Sắp xếp cung cấp một ví dụ tốt về một thuật toán mà rất thường xuyên được sử dụng bởi các nhà khoa học máy tính. Cách đơn giản nhất để sắp xếp một nhóm các mặt hàng là bắt đầu bằng cách loại bỏ các mặt hàng nhỏ nhất trong nhóm, và đặt nó trước tiên. Sau đó, loại bỏ tiếp theo, và đặt nó tiếp theo và như vậy. Thật không may, thuật toán này là O (N2), có nghĩa là số lượng thời gian cần thiết là tỷ lệ thuận với số bình phương. Nếu bạn phải sắp xếp hàng tỉ vấn đề, thuật toán này sẽ mất khoảng 10^18 hoạt động. Để đưa quan điểm này, một máy tính để bàn có thể thực hiện trên 109 thao tác mỗi giây, và phải mất nhiều năm mới hoàn thành việc phân loại hàng tỷ lần theo cách này.

May mắn thay, có một số thuật toán tốt hơn (ví dụ quicksort, heapsort và mergesort) đã được lập ra trong những năm qua, nhiều trong số đó có một thời gian chạy của O (N * Log (N)). Điều này mang lại số lượng hoạt động cần thiết để sắp xếp một tỷ mục xuống một số lượng hợp lý mà ngay cả một máy tính để bàn giá rẻ có thể thực hiện. Thay vì hoạt động của một tỷ bình phương (1018) các thuật toán này chỉ đòi hỏi khoảng 10 tỷ thao tác (10^10), một nhân tố nhanh hơn 100 triệu.

Con đường ngắn nhất

Các thuật toán tìm đường đi ngắn nhất từ ​​điểm này đến điểm khác đã được nghiên cứu trong nhiều năm. Ứng dụng rất nhiều, nhưng hãy giữ mọi thứ đơn giản bằng cách nói rằng chúng ta muốn tìm đường đi ngắn nhất từ ​​điểm A đến điểm B trong một thành phố chỉ với một vài con phố và các giao lộ. Có khá nhiều thuật toán khác nhau đã được phát triển để giải quyết những vấn đề như vậy, tất cả đều có những lợi ích và hạn chế khác nhau. Trước khi chúng tôi nghiên cứu sâu vào nó, hãy cân nhắc xem thuật toán naive - một thuật toán thử mọi tùy chọn có thể tưởng tượng được - sẽ chạy. Nếu thuật toán xem xét mọi đường đi từ A đến B (không đi theo vòng tròn), nó sẽ không kết thúc trong thời gian của chúng ta, ngay cả khi cả A và B đều ở trong một thị trấn nhỏ. Thời gian chạy của thuật toán này là theo kích thước mũ của input, có nghĩa là nó là O (CN) cho một số C. Ngay cả đối với các giá trị nhỏ của C, CN trở nên vô cùng to lớn mặc dù N vừa phải.

Một trong những thuật toán nhanh nhất để giải quyết vấn đề này có thời gian chạy của O (E * V * Log (V)), trong đó E là số đoạn đường, và V là số nút giao cắt. Để đưa quan điểm này, thuật toán sẽ mất khoảng 2 giây để tìm đường đi ngắn nhất trong một thành phố với 10.000 nút giao cắt và 20.000 đoạn đường (thường có khoảng 2 đoạn đường trên mỗi giao lộ). Thuật toán, được gọi là thuật toán của Djikstra, khá phức tạp, và đòi hỏi việc sử dụng một cấu trúc dữ liệu gọi là hàng đợi ưu tiên. Tuy nhiên, trong một số ứng dụng, thậm chí thời gian chạy này cũng quá chậm (xem xét tìm đường đi ngắn nhất từ ​​thành phố New York đến San Francisco - có hàng triệu nút giao thông ở Hoa Kỳ) và các lập trình viên cố gắng làm tốt hơn bằng cách sử dụng những gì được gọi là heuristic. Một heuristic là xấp xỉ của một cái gì đó có liên quan đến một vấn đề, và thường được tính bằng một thuật toán riêng của nó. Ví dụ, trong bài toán về đường đi ngắn nhất, rất hữu ích khi biết khoảng một điểm đến từ đích đến. Biết được điều này cho phép phát triển các thuật toán nhanh hơn (chẳng hạn như A *, một thuật toán đôi khi có thể chạy nhanh hơn đáng kể so với thuật toán của Djikstra) và do đó các lập trình viên đưa ra các heuristics để ước lượng giá trị này. Làm như vậy không phải lúc nào cũng cải thiện thời gian chạy của thuật toán trong trường hợp xấu nhất, nhưng nó làm cho thuật toán nhanh hơn trong hầu hết các ứng dụng trong thế giới thực.

Thuật toán gần đúng

Đôi khi, tuy nhiên, ngay cả những thuật toán tiên tiến nhất, với heuristics tiên tiến nhất, trên các máy tính nhanh nhất là quá chậm. Trong trường hợp này, những hy sinh phải được thực hiện liên quan đến tính đúng đắn của kết quả. Thay vì cố gắng để có được con đường ngắn nhất, một lập trình viên có thể hài lòng để tìm một con đường đó dài hơn nhiều nhất là 10% con đường ngắn nhất.

Trong thực tế, có khá một vài vấn đề quan trọng mà thuật toán nổi tiếng nhất đưa ra câu trả lời tối ưu là không đủ chậm cho hầu hết các mục đích. Nhóm nổi tiếng nhất về những vấn đề này được gọi là NP, viết tắt của đa thức không xác định (đừng lo lắng về ý nghĩa của nó). Khi một vấn đề được gọi là NP - complete hoặc NP - hard, điều đó có nghĩa là không ai biết cách nào tốt nhất để giải quyết chúng một cách tối ưu. Hơn nữa, nếu ai đó đã tìm ra một thuật toán hiệu quả cho một vấn đề NP-complete, thì thuật toán đó sẽ áp dụng cho tất cả các vấn đề NP-complete.

Một ví dụ điển hình của NP-hard là vấn đề người bán hàng nổi tiếng. Một nhân viên bán hàng muốn ghé thăm các thành phố N, và anh ta biết phải mất bao lâu để từ thành phố đến thành phố khác. Câu hỏi đặt ra là "ông ấy có thể thăm tất cả các thành phố nhanh đến mức nào?" Khi thuật toán nhanh nhất để giải quyết vấn đề này thì lại quá chậm - và nhiều người tin rằng điều này sẽ luôn luôn đúng - các lập trình viên tìm các thuật toán đủ nhanh, nhưng không phải giải pháp tối ưu.

Thuật toán ngẫu nhiên

Tuy nhiên, cách tiếp cận khác đối với một số vấn là đề ngẫu nhiên hóa một thuật toán bằng cách nào khác. Trong khi làm như vậy không cải thiện các thuật toán trong trường hợp xấu nhất, nó thường làm cho thuật toán rất tốt trong trường hợp trung bình. Quicksort là một ví dụ điển hình của một thuật toán ngẫu nhiên thường được sử dụng. Trong trường hợp xấu nhất, quicksort phân loại một nhóm các mục trong O (N2), trong đó N là số lượng các mục. Nếu ngẫu nhiên hóa được kết hợp vào thuật toán, tuy nhiên, cơ hội của trường hợp xấu nhất thực sự xảy ra trở nên nhỏ dần, và trung bình, quicksort có một thời gian chạy của O (N * Log (N)). Các thuật toán khác đảm bảo thời gian chạy của O (N * Log (N)), thậm chí trong trường hợp xấu nhất, nhưng chúng chậm hơn trong trường hợp trung bình. Mặc dù cả hai thuật toán đều có tỷ lệ thời gian chạy với N * Log (N), quicksort có một hằng số nhỏ hơn - nghĩa là nó đòi hỏi N * C * N hoạt động, trong khi các thuật toán khác đòi hỏi nhiều hơn như 2 * C * N * Log (N).

Một thuật toán sử dụng các số ngẫu nhiên tìm thấy trung vị của một nhóm các số có thời gian chạy trung bình là O (N). Đây là một cải tiến đáng kể so với việc phân loại các con số và lấy O (N * Log (N)). Hơn nữa, trong khi các thuật toán xác định (không ngẫu nhiên) tồn tại để tìm ra trung vị với thời gian chạy của O (N), thuật toán ngẫu nhiên đơn giản và thường nhanh hơn các thuật toán xác định.

Ý tưởng cơ bản của thuật toán trung vị là chọn một trong số các số trong nhóm một cách ngẫu nhiên, và đếm bao nhiêu trong số các con số trong nhóm ít hơn nó. Cho phép nói rằng có N số, và K trong số đó là ít hơn hoặc bằng với số chúng tôi chọn ngẫu nhiên. Nếu K nhỏ hơn một nửa N, thì chúng ta biết rằng trung vị là số thứ hai (N / 2-K) lớn hơn số ngẫu nhiên chúng ta đã chọn, vì vậy chúng ta loại bỏ các số K nhỏ hơn hoặc bằng với số ngẫu nhiên . Bây giờ, chúng tôi muốn tìm số thứ hai (N / 2-K), thay vì trung vị. Thuật toán cũng giống nhau, và chúng tôi chỉ đơn giản chọn một số khác một cách ngẫu nhiên, và lặp lại các bước trên.

Maximum Flow

Vấn đề lưu lượng tối đa liên quan đến việc xác định cách tốt nhất để có được một số thứ từ nơi này đến nơi khác thông qua một mạng lưới nào đó. Cụ thể hơn, vấn đề đầu tiên nảy sinh liên quan đến mạng lưới đường sắt của Liên bang Xô viết, trong những năm 1950. Hoa Kỳ muốn biết nhanh chóng Liên bang Xô viết có thể cung cấp nguồn cung thông qua mạng lưới đường sắt đến các quốc gia vệ tinh ở Đông Âu.

Ngoài ra, Hoa Kỳ muốn biết đường nào nó có thể phá hủy một cách dễ dàng nhất để cắt đứt các quốc gia vệ tinh từ phần còn lại của Liên Xô. Hóa ra hai vấn đề này liên quan chặt chẽ đến nhau, và giải quyết được vấn đề về dòng chảy tối đa cũng giải quyết vấn đề cắt giảm tối thiểu để tìm ra cách tiết kiệm nhất nhất để cắt đứt Liên Bang Xô Viết khỏi các vệ tinh của nó.

Thuật toán hiệu quả đầu tiên để tìm ra luồng cực đại đã được hai nhà khoa học máy tính, có tên là Ford và Fulkerson. Thuật toán sau đó được đặt tên là thuật toán Ford-Fulkerson, và là một trong những thuật toán nổi tiếng về khoa học máy tính. Trong 50 năm qua, một số cải tiến đã được thực hiện cho thuật toán Ford-Fulkerson để làm cho nó nhanh hơn, một số trong đó là rất phức tạp.

Kể từ khi vấn đề được đặt ra đầu tiên, nhiều ứng dụng bổ sung đã được phát hiện. Thuật toán có sự liên quan rõ ràng với Internet, nơi có được càng nhiều dữ liệu càng tốt từ điểm này đến điểm khác là rất quan trọng. Nó cũng xuất hiện trong nhiều môi trường kinh doanh, và là một phần quan trọng trong nghiên cứu hoạt động. Ví dụ, nếu bạn có nhân viên N và có N công việc cần làm, nhưng không phải mọi nhân viên có thể làm mọi công việc, thuật toán tối đa sẽ cho bạn biết làm thế nào để phân công nhân viên N của bạn để mọi công việc được thực hiện, miễn là có thể.

So sánh trình tự

Nhiều người lập trình trong toàn bộ sự nghiệp của họ mà không bao giờ cần phải thực hiện một thuật toán sử dụng lập trình động. Tuy nhiên, lập trình động xuất hiện trong một số thuật toán quan trọng. Một thuật toán mà hầu hết các lập trình viên có thể đã sử dụng, mặc dù họ có thể không biết đến nó, thấy sự khác biệt giữa hai chuỗi. Cụ thể hơn, nó tính toán số lượng tối thiểu của chèn, xóa, và chỉnh sửa cần thiết để biến đổi chuỗi A thành chuỗi B.

Ví dụ, hãy xem xét hai chuỗi ký tự, "AABAA" và "AAAB". Để biến đổi dãy thứ nhất thành thứ hai, điều đơn giản nhất cần làm là xóa B ở giữa, và thay đổi A cuối thành B. Thuật toán này có nhiều ứng dụng, bao gồm một số vấn đề về DNA và phát hiện sao chép. Tuy nhiên, trong đó hình thức nhiều người lập trình sử dụng nó là khi so sánh hai phiên bản của cùng một tệp mã nguồn. Nếu các phần tử của dãy là các dòng trong tệp tin, thuật toán này có thể cho một lập trình mà các dòng mã đã được gỡ bỏ, những gì đã được chèn, và những cái nào được sửa đổi để từ đó có được một phiên bản kế tiếp.

Nếu không có chương trình động, chúng ta phải xem xét một - phỏng đoán - số lượng mũ của phép biến đổi để có được từ một chuỗi vào khác. Tuy nhiên, nó là một chương trình động làm cho một thuật toán với một thời gian chạy chỉ O (N * M), trong đó N và M là số các phần tử trong hai chuỗi.

Phần kết luận

Các thuật toán khác nhau mà mọi người nghiên cứu cũng khác nhau như các vấn đề mà họ giải quyết. Tuy nhiên, rất có thể là vấn đề bạn đang cố gắng giải quyết tương tự như một vấn đề khác trong một số khía cạnh. Bằng cách phát triển một sự hiểu biết tốt về một phạm vi rộng lớn các thuật toán, bạn sẽ có thể chọn đúng cho vấn đề và áp dụng đúng. Hơn nữa, giải quyết các vấn đề như những điều được tìm thấy trong các cuộc thi sẽ giúp bạn trau dồi kỹ năng của mình trong khía cạnh này. Nhiều vấn đề, mặc dù có vẻ như không thực tế, đòi hỏi cùng phải nghiên cứu một bộ kiến ​​thức thuật toán xuất hiện mỗi ngày trong thế giới thực.

Thuật toán rất quan trọng trong giải quyết những vấn đề trừu tượng, những vấn đề khó mà xử lý bằng phương pháp thông thường sẽ chậm chạm và ì ạch hơn.

Những vấn đề sâu về thuật toán thì có lẽ một người bắt đầu học lập trình như bạn thì không nên quan tâm quá sâu. Lập trình cơ bản cũng không đòi hỏi bạn phải hiễu rõ về thuật toán. Quan trọng là bạn nên học cách tư duy logic từ những thuật toán. Đó là cách bạn sẽ học để giải quyết vấn đề trong lập trình của bạn.

Xem thêm: PH vs ASP.NET? Những điều thực sự bạn nên nhìn nhận thay vì so sánh