Dù bạn là lập trình viên web, mobile hay AI, thì nền tảng thuật toán luôn là chìa khóa để viết code tối ưu, dễ bảo trì và hiệu quả hơn. Nắm chắc các thuật toán cơ bản sẽ giúp bạn không chỉ giải bài tập, mà còn thiết kế hệ thống thông minh và “chạy mượt” trong thực tế.
Dưới đây là 10 thuật toán cơ bản mà bất kỳ lập trình viên nào cũng nên hiểu và biết cách triển khai:
1. Tìm kiếm tuyến tính (Linear Search)
Khái niệm: Tìm từng phần tử một trong danh sách – từ đầu đến cuối. Khi dùng: Khi danh sách nhỏ, không sắp xếp, và không cần hiệu suất cao.
def linear_search(arr, target): for i in range(len(arr)): if arr[i] == target: return i return -1 Ưu điểm: Dễ hiểu, dễ cài đặt Nhược điểm: Chậm nếu mảng lớn (O(n))
2. Tìm kiếm nhị phân (Binary Search)
Khái niệm: Chia đôi mảng đã sắp xếp và tìm kiếm nhanh bằng cách loại bỏ nửa còn lại sau mỗi lần so sánh. Điều kiện: Mảng phải được sắp xếp trước.
def binary_search(arr, target): left, right = 0, len(arr)-1 while left <= right: mid = (left + right) // 2 if arr[mid] == target: return mid elif arr[mid] < target: left = mid + 1 else: right = mid - 1 return -1
Độ phức tạp: O(log n) Dùng nhiều trong: hệ thống tìm kiếm, tự động hoá, kiểm tra tồn tại dữ liệu nhanh.
3. Sắp xếp nổi bọt (Bubble Sort)
Khái niệm: So sánh cặp phần tử kề nhau và hoán đổi nếu sai thứ tự – lặp lại cho đến khi không còn hoán đổi.
def bubble_sort(arr): n = len(arr) for i in range(n): for j in range(0, n-i-1): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j]
Ưu điểm: Hiểu logic dễ, phù hợp cho người mới học Nhược điểm: Chậm (O(n²)), ít dùng trong thực tế
4. Sắp xếp chọn (Selection Sort)
Khái niệm: Tìm phần tử nhỏ nhất và đưa về đầu dãy, rồi tiếp tục với phần còn lại. Hiệu suất tương đương Bubble Sort, nhưng ít hoán đổi hơn.
def selection_sort(arr): for i in range(len(arr)): min_idx = i for j in range(i+1, len(arr)): if arr[j] < arr[min_idx]: min_idx = j arr[i], arr[min_idx] = arr[min_idx], arr[i]
5. Sắp xếp chèn (Insertion Sort)
Khái niệm: Giống cách bạn xếp bài – lấy từng phần tử và chèn vào đúng vị trí trong dãy đã sắp. Hiệu quả với dữ liệu nhỏ hoặc gần sắp xếp sẵn.
def insertion_sort(arr): for i in range(1, len(arr)): key = arr[i] j = i-1 while j >=0 and key < arr[j]: arr[j+1] = arr[j] j -= 1 arr[j+1] = key
Ưu điểm: Tốt với mảng nhỏ Nhược điểm: O(n²) nếu dữ liệu ngẫu nhiên
6. Đệ quy (Recursion)
Khái niệm: Hàm gọi lại chính nó để giải quyết bài toán nhỏ hơn – cho đến khi đạt điều kiện dừng. Ví dụ kinh điển: Tính giai thừa
def factorial(n): if n == 0: return 1 return n * factorial(n - 1)
Lưu ý: Dễ bị lỗi stack overflow nếu không cẩn thận. Phải có điều kiện dừng rõ ràng.
7. Tìm đường đi (DFS – Depth First Search)
Khái niệm: Dò sâu theo một nhánh trước khi quay lại – như đi sâu vào mê cung.
def dfs(graph, start, visited=set()): if start not in visited: print(start) visited.add(start) for neighbor in graph[start]: dfs(graph, neighbor, visited)
Ứng dụng:
- Duyệt cây, đồ thị
- Kiểm tra chu trình
- Tìm tất cả các đường đi
8. Tìm đường đi (BFS – Breadth First Search)
Khái niệm: Duyệt từng lớp – giống như sóng lan ra đều từ điểm bắt đầu.
from collections import deque def bfs(graph, start): visited = set() queue = deque([start]) while queue: node = queue.popleft() if node not in visited: print(node) visited.add(node) queue.extend(graph[node])
Khác với DFS: Tìm đường ngắn nhất trong đồ thị không trọng số.
9. Thuật toán Dijkstra – Tìm đường đi ngắn nhất
Khái niệm: Tìm đường đi ngắn nhất từ 1 điểm đến các điểm còn lại trong đồ thị có trọng số dương. Dùng cấu trúc dữ liệu như heap, priority queue để tối ưu hiệu suất.
Ứng dụng:
- Bản đồ
- Tìm lộ trình giao hàng
- Game, AI tìm đường
10. Quick Sort – sắp xếp nhanh
Khái niệm:
- Chọn một phần tử làm pivot
- Chia mảng thành hai phần: nhỏ hơn và lớn hơn pivot
- Đệ quy sắp xếp hai phần đó
def quick_sort(arr): if len(arr) <= 1: return arr pivot = arr[0] less = [x for x in arr[1:] if x < pivot] greater = [x for x in arr[1:] if x >= pivot] return quick_sort(less) + [pivot] + quick_sort(greater)
Ưu điểm: Rất nhanh (O(n log n)) trong thực tế Nhược điểm: Trường hợp xấu O(n²) nếu chọn pivot không khéo
Kết luận
Bạn không cần học hết mọi thuật toán, nhưng hãy bắt đầu từ những cái gần gũi và ứng dụng cao. Việc nắm chắc 10 thuật toán trên sẽ giúp bạn:
- Tư duy logic tốt hơn
- Viết code gọn, hiệu quả
- Dễ dàng vượt qua các bài test tuyển dụng
- Ứng dụng vào sản phẩm thật (từ tìm kiếm, lọc, sắp xếp, đến tối ưu hiệu năng)
Bài viết được biên tập bởi Từ vựng HSK