Thuật toán là một thuật ngữ khá là quen thuộc trong kỹ thuật, bạn chắc chắn đã từng nghe qua rồi. Nhưng để hiểu rõ khái niệm, đặc điểm và các thuật toán mà một lập trình viên nên biết là gì? Thì chúng ta có thể bắt đầu tìm hiểu trong bài viết dưới đây nhé!
Thuật toán là gì?
Theo wikipedia định nghĩa, thuật toán là:
In mathematics and computer science, an algorithm is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing calculations and data processing.
Hay nói một cách dễ hiểu, thuật toán (Algorithm) là công thức được sử dụng để giúp giải quyết một vấn đề cụ thể. Nó là những phương pháp, bạn chỉ cần làm theo đúng quy trình như vậy sẽ có được kết quả tối ưu.
Đặc điểm nhận biết thuật toán
- Tính chính xác (Precision): là yếu tố quan trọng nhất, mang tính chất khả dụng và khách quan của một thuật toán.
- Tính hữu hạn (Finiteness): một thuật toán phải là hữu hạn, phải có một số lượng giới hạn các lệnh, tức là các lệnh phải đếm được.
- Đầu vào (Input): một thuật toán yêu cầu một số giá trị đầu vào.
- Đầu ra (Output): khi kết thúc một thuật toán, bạn sẽ có một hoặc nhiều kết quả.
- Tính rõ ràng (Unambiguity): một thuật toán hoàn hảo được định nghĩa là không rõ ràng, có nghĩa là các hướng dẫn của nó phải rõ ràng và dễ hiểu.
- Tính độc lập (Independent): một thuật toán nên có hướng dẫn từng bước, điều này phải độc lập với bất kỳ code lập trình nào.
Tại sao cần dùng thuật toán?
Chúng ta cần thuật toán vì những lý do sau:
Nâng cao hiệu quả làm việc
Trong lập trình, có nhiều cách khác nhau để giải quyết một vấn đề. Tuy nhiên, các phương pháp sẽ cho ra hiệu quả và hiệu suất giải quyết vấn đề khác nhau. Vì thế, cần sử dụng thuật toán để vấn đề được giải quyết nhanh giúp nâng cao hiệu suất làm việc hơn.
Khi nói đến lập trình, độ chính xác của phần mềm sẽ cho ra hiệu quả công suất làm việc khác nhau. Với một thuật toán tốt, chương trình máy tính sẽ có thể tạo ra kết quả rất chính xác.
Ngoài ra, bạn có thể dựa vào tốc độ để xem xét hiệu quả làm việc của một phần mềm. Vì thế, bạn cần có thuật toán để rút ngắn thời gian, giúp cải thiện tốc độ của chương trình một cách đáng kể.
Sử dụng hợp lý các nguồn lực
Trong thời gian thực thi chương trình thì máy tính sẽ yêu cầu cần một dung lượng bộ nhớ trống. Sẽ có chương trình chiếm nhiều dung lượng của bộ nhớ hơn những chương trình khác, vì thế việc chọn đúng thuật toán sẽ đảm bảo chương trình đó sử dụng ít bộ nhớ nhất.
11 thuật toán mà một lập trình viên nên biết
Thuật toán sắp xếp (Sorting algorithm)
Trong khoa học máy tính và dữ liệu, việc sắp xếp các tập dữ liệu thô được xem là bước đơn giản nhưng cũng không kém phần quan trọng. Và nó đang ngày càng quan trọng hơn trong thời đại dữ liệu lớn ngày nay.
Dưới đây là các thuật toán sắp xếp phổ biến:
Thuật toán sắp xếp chèn (Insertion Sort)
Insertion sort với cách thức hoạt động có phần tương đồng với thuật toán sắp xếp nổi bọt.
Thuật toán sắp xếp chèn sẽ lần lượt chọn giá trị của các phần tử trong mảng (từ giá trị thứ 2 đến giá trị cuối cùng) và so sánh với với các giá trị phía trước vị trí của nó.
Nếu tìm được vị trí phù hợp, phần tử ấy sẽ được chèn vào vị trí thích hợp giữa các giá trị trước nhưng vẫn đảm bảo mảng được sắp xếp theo thứ tự, đây là một thuật toán nhanh và hiệu quả trên các tập dữ liệu nhỏ.
Thuật toán sắp xếp chọn (Selection Sort)
Selection Sort là một thuật toán sắp xếp đơn giản dựa trên so sánh tại chỗ. Với sắp xếp chọn, dữ liệu được chia thành hai phần "đã sắp xếp" và "không được sắp xếp".
Thuật toán sẽ quét phần chưa được sắp xếp để tìm giá trị nhỏ nhất và chuyển nó đến phần đã sắp xếp (bên trái danh sách), danh sách được chia thành hai phần (trái - phải). Phần được sắp xếp ở đầu bên trái và phần chưa được sắp xếp ở đầu bên phải
Sau đó, nó sẽ lặp lại quá trình này, dần dần sẽ xây dựng được một mảng và được sắp xếp theo thứ tự tăng dần, thuật toán này phù hợp với các tập dữ liệu nhỏ.
Thuật toán sắp xếp nổi bọt (Bubble Sort)
Bubble Sort là một thuật toán sắp xếp đơn giản, hoạt động bằng cách quét qua mọi mục trong danh sách và hoán đổi các mục liền kề nếu chúng đứng không đúng thứ tự.
Có thể tiến hành từ trên xuống (bên trái sang) hoặc từ dưới lên (bên phải sang). Quá trình này được lặp lại cho đến khi không có phần tử nào trong danh sách bị thay thế.
Ví dụ: trong một dãy số ngẫu nhiên, bạn muốn sắp xếp theo thứ tự tăng dần, lúc này thuật toán sẽ chuyển tập hợp nhiều lần cho đến khi tất cả các số phù hợp với dãy.
Thuật toán sắp xếp nhanh (Quick Sort)
Quick sort là một thuật toán áp dụng cách thức "chia để trị" (Divide and Conquer) vì nó chia nhỏ cấu trúc dữ liệu thành các mảng nhỏ và sắp xếp một cách nhanh chóng.
Thuật toán sẽ chọn 1 phần tử trong dãy làm phần tử chốt p (pivot). Sau đó, chúng sẽ phân đoạn: chia dãy đã cho thành 2 dãy con, dãy con trái(L) sẽ gồm những phần tử nhỏ hơn phần tử chốt và dãy con phải(R) là những phần tử lớn hơn phần tử chốt.
Quá trình được lặp lại trong các mảng nhỏ này cho đến khi mỗi danh sách chỉ có một mục, lúc đó toàn bộ chuỗi sẽ được đặt hàng.
Thuật toán sắp xếp trộn (Merge Sort)
Merge Sort dùng phương pháp chia để trị giống thuật toán sắp xếp nhanh (Quick Sort) để giải quyết các bài toán có dữ liệu lớn và phức tạp.
Đối với bài toán sắp xếp, nó sẽ chia cấu trúc dữ liệu thành các nửa cho đến khi mỗi danh sách con chỉ có một hoặc hai mục.
Sau đó, chúng được đặt theo thứ tự cần thiết, và cuối cùng, tất cả các danh sách con được hợp nhất với nhau đúng thứ tự theo phương pháp trộn tự nhiên.
Thuật toán tìm kiếm (Searching Algorithms)
Tìm kiếm được xem là chức năng cơ bản nhất trong IT, được xem cơ bản là thế nhưng nó lại đóng vai trò rất quan trọng trong lập trình.
Nó có thể liên quan đến việc tìm kiếm trong cơ sở dữ liệu nội bộ để tìm một phần thông tin cụ thể và có hai cách tiếp cận được sử dụng ngày nay.
Thuật toán tìm kiếm tuyến tính (Linear Search)
Thuật toán tìm kiếm tuyến tính (Linear Search) hay còn được gọi là tìm kiếm tuần tự (Sequential Search).
Đây là một thuật toán đơn giản, chúng được sử dụng để tìm một phần tử hoặc thông tin cụ thể trong một tập dữ liệu chưa được sắp xếp.
Ví dụ: nếu bạn cần truy xuất một số điện thoại di động từ một cơ sở dữ liệu khổng lồ, thuật toán tìm kiếm tuyến tính sẽ đi qua từng số một cho đến khi tìm thấy mục có liên quan.
Thuận toán tìm kiếm nhị phân (Binary Search)
Binary Search tìm kiếm dữ liệu theo khoảng thời gian thay vì tuần tự, vì không cần phải quét toàn bộ chuỗi nên nó được xem là hiệu quả hơn khi sử dụng trên các cấu trúc dữ liệu dạng mảng được sắp xếp.
Ví dụ: Chúng sẽ chia đôi mảng thành hai phần gọi là left và right, trong một chuỗi dài các số tăng dần, tìm kiếm nhị phân sẽ bắt đầu với phần tử ở giữa gọi là mid.
Chúng ta sẽ dựa vào mid để tìm xem giá trị chúng ta cần tìm nó nằm bên left hay right. Nếu giá trị cần tìm nằm bên left thì chúng sẽ loại bỏ mảng right và chỉ thực hiện tìm kiếm trên left và ngược lại.
Quá trình này sẽ tiếp tục cho đến khi nó tìm thấy mục hoặc không còn danh sách phụ nào.
Thuật toán đồ thị (Graph Algorithms)
Đồ thị là một công cụ quan trọng trong trực quan hóa dữ liệu (Data Visualization), chúng thường được sử dụng để biểu diễn các mục dữ liệu dưới dạng các nút (nodes) được kết nối với nhau trong một mạng.
Thuận toán tìm kiếm theo chiều rộng (Breadth-First Search)
Breadth-First Search (viết tắt là BFS) duyệt đồ thị theo chiều rộng và sử dụng hàng đợi (queue) để ghi nhớ đỉnh liền kề để bắt đầu việc tìm kiếm khi trong bất kỳ vòng lặp nào.
Đây được xem là phương pháp hữu ích giúp tìm đường đi ngắn nhất qua các node của cấu trúc đồ thị.
Thuận toán tìm kiếm theo chiều sâu (Depth-First Search)
Depth-First Search (viết tắt là DFS) sẽ chọn một node gốc và sau đó triển khai khám phá càng nhiều, sẽ cho ra dọc theo một nhánh dẫn đến từ nó (và bao gồm cả các nhánh con của nó)
Sau đó, nó sẽ quay trở lại dọc theo nhánh tới gốc và bắt đầu lại quá trình dọc theo nhánh khác. Đây được xem là thuật toán phù hợp khi node đích cách xa nguồn.
Thuật toán tìm đường đi ngắn nhất Dijkstra (Shortest-Path)
Thuật toán Dijkstra dùng để giải quyết bài toán đường đi ngắn nhất một nguồn (Single-source shortest path).
Thuật toán này được đặt theo tên nhà khoa học máy tính người Hà Lan Edsger W. Ứng dụng nổi tiếng nhất của thuật toán này là với bản đồ Google, nó tính toán nhanh chóng tuyến đường nhanh nhất giữa hai điểm bất kỳ trên bản đồ và luôn được cập nhật liên tục.
Thuật toán Kruskal và Prim
Thuật toán Kruskal và Prim là hai thuật toán "tham lam" được sử dụng để tìm cây bao trùm nhỏ nhất (MST) của cấu trúc đồ thị liên thông có trọng số. MST có nghĩa là trọng số tối thiểu của các cạnh được sử dụng để kết nối các nút (hoặc đỉnh) trong một cấu trúc đồ thị.
Thuật toán Kruskal thêm các cạnh có trọng số thấp nhất trong một cấu trúc cho đến khi chúng kết nối với nhau để tạo thành MST.
Thuật toán Prim tìm MST bằng cách bắt đầu với một đỉnh ngẫu nhiên và xây dựng đến đỉnh tiếp theo thông qua các cạnh có trọng số thấp nhất.
Lời kết
200Lab mong là thông qua bài viết này bạn đã nắm được các thuật toán khác nhau sẽ đóng những vai trò khác nhau trong lập trình. Bạn chỉ cần xác định vấn đề của mình và sau đó chọn thuật toán phù hợp để sử dụng.
Chúc bạn thành công nhé!
