🔍 8 Thuật Toán Cơ Bản Mọi Lập Trình Viên Nên Biết

 

🔍 8 Thuật Toán Cơ Bản Mọi Lập Trình Viên Nên Biết

Thuật toán là nền tảng cốt lõi của lập trình. Dù bạn làm web, mobile hay AI, hiểu về các thuật toán cơ bản sẽ giúp bạn giải quyết vấn đề nhanh hơn, viết code tối ưu hơn.

Dưới đây là 8 thuật toán quan trọng nhất bạn nên biết – cùng ví dụ code Python minh họa thực tế, dễ hiểu.

---

1. Sắp xếp (Sorting)

Thuật toán sắp xếp giúp đưa dữ liệu về đúng thứ tự. Dù bạn làm bảng, lọc dữ liệu hay phân loại sản phẩm, bạn đều cần đến nó.

Ví dụ: Bubble Sort

python
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]
    return arr

📌 Bubble Sort đơn giản nhưng chậm (O(n²)). Học để hiểu tư duy, còn thực tế thì dùng Merge Sort hoặc Quick Sort.

---

2. Tìm kiếm (Searching)

Khi cần tìm kiếm nhanh trong danh sách – như tìm tên sản phẩm, user ID – bạn sẽ dùng thuật toán tìm kiếm.

Ví dụ: Binary Search

python
def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

📌 Yêu cầu mảng đã sắp xếp. Thời gian chạy O(log n) – rất tối ưu.

---

3. Thuật toán đồ thị (Graph)

Dữ liệu kết nối như bản đồ, mạng xã hội, sơ đồ tuyến xe buýt – đều là bài toán đồ thị.

Ví dụ: Breadth-First Search (BFS)

python
from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            visited.add(vertex)
            queue.extend(set(graph[vertex]) - visited)
    return visited

📌 BFS dùng để tìm đường ngắn nhất trong đồ thị không trọng số.

---

4. Quy hoạch động (Dynamic Programming - DP)

Nếu bạn thấy bài toán có lặp lại nhiều bước giống nhau → đó là lúc nên dùng DP để ghi nhớ kết quả và tránh tính lại.

Ví dụ: Tính Fibonacci

python
def fibonacci(n):
    dp = [0, 1]
    for i in range(2, n+1):
        dp.append(dp[i-1] + dp[i-2])
    return dp[n]

📌 Rất phù hợp với bài toán cái ba lô (knapsack), chia tiền, xếp hình...

---

5. Tham lam (Greedy)

Giải từng bước một bằng cách chọn phương án tối ưu ở hiện tại – nhanh, đơn giản nhưng không phải lúc nào cũng đúng.

Ví dụ: Fractional Knapsack (tham lam chọn theo tỉ lệ)

python
def fractional_knapsack(items, capacity):
    items.sort(key=lambda x: x[1]/x[0], reverse=True)
    total = 0
    for weight, value in items:
        if capacity >= weight:
            capacity -= weight
            total += value
        else:
            total += value * (capacity / weight)
            break
    return total

📌 Dùng khi có thể chia nhỏ (fractional). Nếu là “0/1 knapsack” → dùng DP.

---

6. Chia để trị (Divide and Conquer)

Chia nhỏ vấn đề, giải từng phần, rồi ghép lại → nhanh và hiệu quả.

Ví dụ: Merge Sort

python
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr)//2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

📌 Đây là nền tảng để học các kỹ thuật đệ quy cao cấp hơn.

---

7. Quay lui (Backtracking)

Thử – sai – quay lại nếu sai. Rất mạnh cho bài toán tổ hợp như sudoku, xếp quân cờ, chọn đường đi...

Ví dụ: Giải Sudoku

python
def solve_sudoku(board):
    for i in range(9):
        for j in range(9):
            if board[i][j] == 0:
                for num in range(1, 10):
                    if is_valid(board, i, j, num):
                        board[i][j] = num
                        if solve_sudoku(board):
                            return True
                        board[i][j] = 0
                return False
    return True

📌 Quay lui rất mạnh nhưng cũng rất tốn thời gian nếu không cắt nhánh tốt.

---

8. Thuật toán ngẫu nhiên (Randomized)

Dùng ngẫu nhiên để cải thiện tốc độ hoặc tránh trường hợp xấu nhất.

Ví dụ: Randomized Quick Sort

python
import random

def randomized_quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = random.choice(arr)
    left = [x for x in arr if x < pivot]
    mid = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return randomized_quick_sort(left) + mid + randomized_quick_sort(right)

📌 Dễ cài đặt, tránh trường hợp “tệ nhất” của Quick Sort thông thường.

---

🎯 Tổng kết

Tên thuật toán	Ứng dụng thực tế
Sorting	Lọc, sắp xếp danh sách, bảng dữ liệu
Searching	Tìm kiếm nhanh trong danh sách
Graph	Mạng xã hội, bản đồ, kết nối dữ liệu
Dynamic Programming	Tối ưu hóa, quyết định có ràng buộc
Greedy	Lấy theo giá trị tốt nhất hiện tại
Divide & Conquer	Giải bài toán lớn bằng cách chia nhỏ
Backtracking	Liệt kê tổ hợp, sudoku, game logic
Randomized	Tối ưu hiệu suất, tránh trường hợp xấu

---

🚀 Gợi ý học:
Luyện tập những thuật toán này qua LeetCode, HackerRank hoặc Codeforces để tăng kỹ năng giải quyết vấn đề và chuẩn bị phỏng vấn tốt hơn.

---

📌 #ThuậtToán #LậpTrình #Sorting #DP #Greedy #Graph #Backtracking #DivideAndConquer #DevLife #NguồnTinViệt