Mục lục#

Thuật toán tìm kiếm
- Linear Search (Tìm kiếm tuyến tính)
- Binary Search (Tìm kiếm nhị phân)
Thuật toán sắp xếp
Cấu trúc dữ liệu cơ bản
- Stack (Ngăn xếp)
- Queue (Hàng đợi)
Thuật toán đồ thị
- Depth-First Search (DFS)
- Breadth-First Search (BFS)
Thuật toán quy hoạch động (Dynamic Programming)
- Fibonacci với memoization
- Longest Common Subsequence (LCS)
Thuật toán tham lam (Greedy)
- Activity Selection Problem
Thuật toán chia để trị (Divide and Conquer)
- Strassen’s Matrix Multiplication
Thuật toán đồ thị & cấu trúc dữ liệu nâng cao
Binary Tree (Cây nhị phân)
Linked List (Danh sách liên kết đơn)
Kết luận

Các thuật toán cơ bản mà mọi lập trình viên cần biết 🧮#

Thuật toán là nền tảng của lập trình và khoa học máy tính. Trong bài viết này, tôi sẽ chia sẻ những thuật toán cơ bản quan trọng mà mọi lập trình viên nên nắm vững.

1. Thuật toán tìm kiếm#

Linear Search (Tìm kiếm tuyến tính)#

1
#include <vector>
2
using namespace std;
3

4
// Tìm kiếm tuyến tính trong mảng
5
int linear_search(const vector<int>& arr, int target) {
6
    for (int i = 0; i < arr.size(); ++i) {
7
        if (arr[i] == target) return i;
8
    }
9
    return -1;
10
}
11

12
// Độ phức tạp: O(n)
13
// Không gian: O(1)

Binary Search (Tìm kiếm nhị phân)#

1
#include <vector>
2
using namespace std;
3

4
// Tìm kiếm nhị phân trong mảng đã sắp xếp
5
int binary_search(const vector<int>& arr, int target) {
6
    int left = 0, right = arr.size() - 1;
7
    while (left <= right) {
8
        int mid = left + (right - left) / 2;
9
        if (arr[mid] == target) return mid;
10
        else if (arr[mid] < target) left = mid + 1;
11
        else right = mid - 1;
12
    }
13
    return -1;
14
}
15

16
// Độ phức tạp: O(log n)
17
// Không gian: O(1)
18
// Yêu cầu: Mảng đã được sắp xếp

2. Thuật toán sắp xếp#

Bubble Sort#

1
#include <vector>
2
using namespace std;
3

4
// Sắp xếp nổi bọt
5
void bubble_sort(vector<int>& arr) {
6
    int n = arr.size();
7
    for (int i = 0; i < n; ++i) {
8
        for (int j = 0; j < n - i - 1; ++j) {
9
            if (arr[j] > arr[j + 1]) {
10
                swap(arr[j], arr[j + 1]);
11
            }
12
        }
13
    }
14
}
15
// Độ phức tạp: O(n^2)
16
// Không gian: O(1)

Quick Sort#

1
#include <vector>
2
using namespace std;
3

4
// Sắp xếp nhanh (Quick Sort)
5
void quick_sort(vector<int>& arr, int left, int right) {
6
    if (left >= right) return;
7
    int pivot = arr[left + (right - left) / 2];
8
    int i = left, j = right;
9
    while (i <= j) {
10
        while (arr[i] < pivot) ++i;
11
        while (arr[j] > pivot) --j;
12
        if (i <= j) {
13
            swap(arr[i], arr[j]);
14
            ++i; --j;
15
        }
16
    }
17
    if (left < j) quick_sort(arr, left, j);
18
    if (i < right) quick_sort(arr, i, right);
19
}
20
// Độ phức tạp trung bình: O(n log n)
21
// Độ phức tạp xấu nhất: O(n^2)
22
// Không gian: O(log n)

Merge Sort#

1
#include <vector>
2
using namespace std;
3

4
// Hợp hai mảng con đã sắp xếp
5
void merge(vector<int>& arr, int left, int mid, int right) {
6
    int n1 = mid - left + 1;
7
    int n2 = right - mid;
8
    vector<int> L(n1), R(n2);
9
    for (int i = 0; i < n1; ++i) L[i] = arr[left + i];
10
    for (int j = 0; j < n2; ++j) R[j] = arr[mid + 1 + j];
11
    int i = 0, j = 0, k = left;
12
    while (i < n1 && j < n2) {
13
        if (L[i] <= R[j]) arr[k++] = L[i++];
14
        else arr[k++] = R[j++];
15
    }
16
    while (i < n1) arr[k++] = L[i++];
17
    while (j < n2) arr[k++] = R[j++];
18
}
19

20
// Sắp xếp trộn (Merge Sort)
21
void merge_sort(vector<int>& arr, int left, int right) {
22
    if (left >= right) return;
23
    int mid = left + (right - left) / 2;
24
    merge_sort(arr, left, mid);
25
    merge_sort(arr, mid + 1, right);
26
    merge(arr, left, mid, right);
27
}
28
// Độ phức tạp: O(n log n)
29
// Không gian: O(n)

3. Cấu trúc dữ liệu cơ bản#

Stack (Ngăn xếp)#

1
#include <vector>
2
#include <iostream>
3
using namespace std;
4

5
// Cấu trúc dữ liệu ngăn xếp (Stack)
6
class Stack {
7
    vector<int> items;
8
public:
9
    void push(int item) { items.push_back(item); }
10
    void pop() { if (!is_empty()) items.pop_back(); }
11
    int top() const { return is_empty() ? -1 : items.back(); }
12
    bool is_empty() const { return items.empty(); }
13
    int size() const { return items.size(); }
14
};
15

16
// Độ phức tạp các thao tác: O(1)

Queue (Hàng đợi)#

1
#include <queue>
2
using namespace std;
3

4
// Cấu trúc dữ liệu hàng đợi (Queue)
5
class Queue {
6
    queue<int> items;
7
public:
8
    void enqueue(int item) { items.push(item); }
9
    void dequeue() { if (!is_empty()) items.pop(); }
10
    int front() const { return is_empty() ? -1 : items.front(); }
11
    bool is_empty() const { return items.empty(); }
12
    int size() const { return items.size(); }
13
};
14

15
// Độ phức tạp các thao tác: O(1)

4. Thuật toán đồ thị#

Depth-First Search (DFS)#

1
#include <vector>
2
#include <unordered_set>
3
#include <unordered_map>
4

5
class Graph {
6
private:
7
    std::unordered_map<int, std::vector<int>> adjacencyList;
8

9
public:
10
    void addEdge(int from, int to) {
11
        adjacencyList[from].push_back(to);
12
        adjacencyList[to].push_back(from); // Undirected graph
13
    }
14

15
    void dfs(int start) {
16
        std::unordered_set<int> visited;
17
        dfsHelper(start, visited);
18
    }
19

20
private:
21
    void dfsHelper(int node, std::unordered_set<int>& visited) {
22
        visited.insert(node);
23
        std::cout << node << " ";
24

25
        for (int neighbor : adjacencyList[node]) {
26
            if (visited.find(neighbor) == visited.end()) {
27
                dfsHelper(neighbor, visited);
28
            }
29
        }
30
    }
31
};
32

33
// Độ phức tạp: O(V + E)
34
// V: số đỉnh, E: số cạnh

Breadth-First Search (BFS)#

1
#include <queue>
2

3
void Graph::bfs(int start) {
4
    std::unordered_set<int> visited;
5
    std::queue<int> q;
6

7
    visited.insert(start);
8
    q.push(start);
9

10
    while (!q.empty()) {
11
        int current = q.front();
12
        q.pop();
13
        std::cout << current << " ";
14

15
        for (int neighbor : adjacencyList[current]) {
16
            if (visited.find(neighbor) == visited.end()) {
17
                visited.insert(neighbor);
18
                q.push(neighbor);
19
            }
20
        }
21
    }
22
}
23

24
// Độ phức tạp: O(V + E)
25
// V: số đỉnh, E: số cạnh

5. Thuật toán quy hoạch động (Dynamic Programming)#

Fibonacci với memoization#

1
#include <vector>
2
using namespace std;
3

4
// Tính Fibonacci sử dụng memoization (quy hoạch động)
5
int fibonacci_memo(int n, vector<int>& memo) {
6
    if (n <= 1) return n;
7
    if (memo[n] != -1) return memo[n];
8
    return memo[n] = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo);
9
}
10
// Sử dụng: vector<int> memo(n+1, -1); fibonacci_memo(n, memo);
11
// Độ phức tạp: O(n)
12
// Không gian: O(n)

Longest Common Subsequence (LCS)#

1
#include <vector>
2
#include <string>
3
using namespace std;
4

5
// Tìm độ dài dãy con chung dài nhất (LCS)
6
int lcs(const string& s1, const string& s2) {
7
    int m = s1.size(), n = s2.size();
8
    vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
9
    for (int i = 1; i <= m; ++i) {
10
        for (int j = 1; j <= n; ++j) {
11
            if (s1[i-1] == s2[j-1])
12
                dp[i][j] = dp[i-1][j-1] + 1;
13
            else
14
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
15
        }
16
    }
17
    return dp[m][n];
18
}
19
// Độ phức tạp: O(m*n)
20
// Không gian: O(m*n)

6. Thuật toán tham lam (Greedy)#

Activity Selection Problem#

1
#include <vector>
2
#include <algorithm>
3
using namespace std;
4

5
// Bài toán chọn hoạt động (Activity Selection)
6
struct Activity {
7
    int start, finish;
8
};
9

10
bool cmp(const Activity& a, const Activity& b) {
11
    return a.finish < b.finish;
12
}
13

14
vector<int> activity_selection(vector<Activity>& activities) {
15
    int n = activities.size();
16
    sort(activities.begin(), activities.end(), cmp);
17
    vector<int> selected;
18
    selected.push_back(0); // chọn hoạt động đầu tiên
19
    int last = 0;
20
    for (int i = 1; i < n; ++i) {
21
        if (activities[i].start >= activities[last].finish) {
22
            selected.push_back(i);
23
            last = i;
24
        }
25
    }
26
    return selected;
27
}
28
// Độ phức tạp: O(n log n) (do sắp xếp)
29
// Không gian: O(1)

7. Thuật toán chia để trị (Divide and Conquer)#

Strassen’s Matrix Multiplication#

1
#include <vector>
2
using namespace std;
3

4
typedef vector<vector<int>> Matrix;
5

6
// Cộng hai ma trận vuông
7
Matrix matrix_add(const Matrix& A, const Matrix& B) {
8
    int n = A.size();
9
    Matrix C(n, vector<int>(n));
10
    for (int i = 0; i < n; ++i)
11
        for (int j = 0; j < n; ++j)
12
            C[i][j] = A[i][j] + B[i][j];
13
    return C;
14
}
15

16
// Trừ hai ma trận vuông
17
Matrix matrix_subtract(const Matrix& A, const Matrix& B) {
18
    int n = A.size();
19
    Matrix C(n, vector<int>(n));
20
    for (int i = 0; i < n; ++i)
21
        for (int j = 0; j < n; ++j)
22
            C[i][j] = A[i][j] - B[i][j];
23
    return C;
24
}
25

26
// Nhân ma trận bằng thuật toán Strassen
27
Matrix strassen_multiply(const Matrix& A, const Matrix& B) {
28
    int n = A.size();
29
    if (n == 1) return Matrix{{A[0][0] * B[0][0]}};
30
    int mid = n / 2;
31
    // Chia ma trận thành 4 phần
32
    Matrix A11(mid, vector<int>(mid)), A12(mid, vector<int>(mid)),
33
           A21(mid, vector<int>(mid)), A22(mid, vector<int>(mid)),
34
           B11(mid, vector<int>(mid)), B12(mid, vector<int>(mid)),
35
           B21(mid, vector<int>(mid)), B22(mid, vector<int>(mid));
36
    for (int i = 0; i < mid; ++i) {
37
        for (int j = 0; j < mid; ++j) {
38
            A11[i][j] = A[i][j];
39
            A12[i][j] = A[i][j + mid];
40
            A21[i][j] = A[i + mid][j];
41
            A22[i][j] = A[i + mid][j + mid];
42
            B11[i][j] = B[i][j];
43
            B12[i][j] = B[i][j + mid];
44
            B21[i][j] = B[i + mid][j];
45
            B22[i][j] = B[i + mid][j + mid];
46
        }
47
    }
48
    // 7 phép nhân con
49
    Matrix P1 = strassen_multiply(A11, matrix_subtract(B12, B22));
50
    Matrix P2 = strassen_multiply(matrix_add(A11, A12), B22);
51
    Matrix P3 = strassen_multiply(matrix_add(A21, A22), B11);
52
    Matrix P4 = strassen_multiply(A22, matrix_subtract(B21, B11));
53
    Matrix P5 = strassen_multiply(matrix_add(A11, A22), matrix_add(B11, B22));
54
    Matrix P6 = strassen_multiply(matrix_subtract(A12, A22), matrix_add(B21, B22));
55
    Matrix P7 = strassen_multiply(matrix_subtract(A11, A21), matrix_add(B11, B12));
56
    // Tính các phần tử của ma trận kết quả
57
    Matrix C11 = matrix_add(matrix_subtract(matrix_add(P5, P4), P2), P6);
58
    Matrix C12 = matrix_add(P1, P2);
59
    Matrix C21 = matrix_add(P3, P4);
60
    Matrix C22 = matrix_subtract(matrix_subtract(matrix_add(P5, P1), P3), P7);
61
    // Ghép các phần lại
62
    Matrix C(n, vector<int>(n));
63
    for (int i = 0; i < mid; ++i) {
64
        for (int j = 0; j < mid; ++j) {
65
            C[i][j] = C11[i][j];
66
            C[i][j + mid] = C12[i][j];
67
            C[i + mid][j] = C21[i][j];
68
            C[i + mid][j + mid] = C22[i][j];
69
        }
70
    }
71
    return C;
72
}
73
// Độ phức tạp: O(n^2.807)

8. Thuật toán đồ thị & cấu trúc dữ liệu nâng cao#

Dijkstra - Đường đi ngắn nhất trên đồ thị có trọng số dương#

1
#include <vector>
2
#include <queue>
3
#include <climits>
4

5
struct Edge {
6
    int to;
7
    int weight;
8

9
    Edge(int t, int w) : to(t), weight(w) {}
10
};
11

12
class WeightedGraph {
13
private:
14
    std::vector<std::vector<Edge>> graph;
15
    int vertices;
16

17
public:
18
    WeightedGraph(int v) : vertices(v) {
19
        graph.resize(v);
20
    }
21

22
    void addEdge(int from, int to, int weight) {
23
        graph[from].push_back(Edge(to, weight));
24
        graph[to].push_back(Edge(from, weight)); // Undirected
25
    }
26

27
    std::vector<int> dijkstra(int start) {
28
        std::vector<int> dist(vertices, INT_MAX);
29
        std::priority_queue<std::pair<int, int>,
30
                          std::vector<std::pair<int, int>>,
31
                          std::greater<std::pair<int, int>>> pq;
32

33
        dist[start] = 0;
34
        pq.push({0, start});
35

36
        while (!pq.empty()) {
37
            int u = pq.top().second;
38
            pq.pop();
39

40
            for (const Edge& edge : graph[u]) {
41
                int v = edge.to;
42
                int weight = edge.weight;
43

44
                if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
45
                    dist[v] = dist[u] + weight;
46
                    pq.push({dist[v], v});
47
                }
48
            }
49
        }
50

51
        return dist;
52
    }
53
};
54
// Độ phức tạp: O((V+E) log V)

Bellman-Ford - Đường đi ngắn nhất với trọng số âm#

1
#include <vector>
2
#include <limits>
3
using namespace std;
4

5
struct EdgeBF {
6
    int u, v, w;
7
};
8

9
vector<int> bellman_ford(int n, const vector<EdgeBF>& edges, int start) {
10
    vector<int> dist(n, numeric_limits<int>::max());
11
    dist[start] = 0;
12
    for (int i = 1; i < n; ++i) {
13
        for (const auto& e : edges) {
14
            if (dist[e.u] < numeric_limits<int>::max() && dist[e.v] > dist[e.u] + e.w)
15
                dist[e.v] = dist[e.u] + e.w;
16
        }
17
    }
18
    // Kiểm tra chu trình âm
19
    for (const auto& e : edges) {
20
        if (dist[e.u] < numeric_limits<int>::max() && dist[e.v] > dist[e.u] + e.w)
21
            throw runtime_error("Đồ thị có chu trình âm");
22
    }
23
    return dist;
24
}
25
// Độ phức tạp: O(V*E)

Floyd-Warshall - Đường đi ngắn nhất giữa mọi cặp đỉnh#

1
#include <vector>
2
#include <climits>
3

4
std::vector<std::vector<int>> floydWarshall(const std::vector<std::vector<int>>& graph) {
5
    int n = graph.size();
6
    std::vector<std::vector<int>> dist = graph;
7

8
    for (int k = 0; k < n; k++) {
9
        for (int i = 0; i < n; i++) {
10
            for (int j = 0; j < n; j++) {
11
                if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX &&
12
                    dist[i][k] + dist[k][j] < dist[i][j]) {
13
                    dist[i][j] = dist[i][k] + dist[k][j];
14
                }
15
            }
16
        }
17
    }
18

19
    return dist;
20
}
21
// Độ phức tạp: O(V^3)

Kruskal - Cây khung nhỏ nhất (Minimum Spanning Tree)#

1
#include <vector>
2
#include <algorithm>
3
using namespace std;
4

5
struct Edge {
6
    int u, v, w;
7
    bool operator<(const Edge& other) const { return w < other.w; }
8
};
9

10
struct DSU {
11
    vector<int> parent, rank;
12
    DSU(int n) : parent(n), rank(n, 0) { for (int i = 0; i < n; ++i) parent[i] = i; }
13
    int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }
14
    bool unite(int x, int y) {
15
        x = find(x); y = find(y);
16
        if (x == y) return false;
17
        if (rank[x] < rank[y]) swap(x, y);
18
        parent[y] = x;
19
        if (rank[x] == rank[y]) ++rank[x];
20
        return true;
21
    }
22
};
23

24
int kruskal(int n, vector<Edge>& edges) {
25
    sort(edges.begin(), edges.end());
26
    DSU dsu(n);
27
    int mst_weight = 0;
28
    for (const Edge& e : edges) {
29
        if (dsu.unite(e.u, e.v)) mst_weight += e.w;
30
    }
31
    return mst_weight;
32
}
33
// Độ phức tạp: O(E log E)

Edmonds-Karp - Luồng cực đại (Maximum Flow)#

1
#include <vector>
2
#include <queue>
3
#include <algorithm>
4
using namespace std;
5

6
int edmonds_karp(int n, vector<vector<int>>& capacity, int s, int t) {
7
    vector<vector<int>> flow(n, vector<int>(n, 0));
8
    int max_flow = 0;
9
    while (true) {
10
        vector<int> parent(n, -1);
11
        queue<int> q;
12
        q.push(s);
13
        parent[s] = s;
14
        while (!q.empty() && parent[t] == -1) {
15
            int u = q.front(); q.pop();
16
            for (int v = 0; v < n; ++v) {
17
                if (parent[v] == -1 && capacity[u][v] - flow[u][v] > 0) {
18
                    parent[v] = u;
19
                    q.push(v);
20
                }
21
            }
22
        }
23
        if (parent[t] == -1) break;
24
        int aug = 1e9;
25
        for (int v = t; v != s; v = parent[v])
26
            aug = min(aug, capacity[parent[v]][v] - flow[parent[v]][v]);
27
        for (int v = t; v != s; v = parent[v]) {
28
            flow[parent[v]][v] += aug;
29
            flow[v][parent[v]] -= aug;
30
        }
31
        max_flow += aug;
32
    }
33
    return max_flow;
34
}
35
// Độ phức tạp: O(V*E^2)

Heap (Min Heap)#

1
#include <queue>
2
#include <vector>
3
using namespace std;
4

5
// Min Heap sử dụng priority_queue
6
priority_queue<int, vector<int>, greater<int>> min_heap;
7
// Các thao tác: push(x), pop(), top(), empty()
8
// Độ phức tạp: O(log n) cho push/pop

Union-Find (Disjoint Set)#

1
#include <vector>
2
using namespace std;
3

4
struct UnionFind {
5
    vector<int> parent, rank;
6
    UnionFind(int n) : parent(n), rank(n, 0) { for (int i = 0; i < n; ++i) parent[i] = i; }
7
    int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }
8
    void unite(int x, int y) {
9
        x = find(x); y = find(y);
10
        if (x == y) return;
11
        if (rank[x] < rank[y]) swap(x, y);
12
        parent[y] = x;
13
        if (rank[x] == rank[y]) ++rank[x];
14
    }
15
    bool same(int x, int y) { return find(x) == find(y); }
16
};
17
// Độ phức tạp: gần O(1) cho mỗi thao tác

Trie (Cây tiền tố)#

1
#include <string>
2
#include <vector>
3
using namespace std;
4

5
struct TrieNode {
6
    vector<TrieNode*> children;
7
    bool is_end;
8
    TrieNode() : children(26, nullptr), is_end(false) {}
9
};
10

11
struct Trie {
12
    TrieNode* root;
13
    Trie() : root(new TrieNode()) {}
14
    void insert(const string& word) {
15
        TrieNode* node = root;
16
        for (char c : word) {
17
            int idx = c - 'a';
18
            if (!node->children[idx]) node->children[idx] = new TrieNode();
19
            node = node->children[idx];
20
        }
21
        node->is_end = true;
22
    }
23
    bool search(const string& word) {
24
        TrieNode* node = root;
25
        for (char c : word) {
26
            int idx = c - 'a';
27
            if (!node->children[idx]) return false;
28
            node = node->children[idx];
29
        }
30
        return node->is_end;
31
    }
32
};
33
// Độ phức tạp: O(L) với L là độ dài từ

Topological Sort (Sắp xếp topo)#

1
#include <vector>
2
#include <queue>
3
using namespace std;
4

5
vector<int> topo_sort(int n, const vector<vector<int>>& adj) {
6
    vector<int> indeg(n, 0);
7
    for (int u = 0; u < n; ++u)
8
        for (int v : adj[u]) ++indeg[v];
9
    queue<int> q;
10
    for (int i = 0; i < n; ++i) if (indeg[i] == 0) q.push(i);
11
    vector<int> order;
12
    while (!q.empty()) {
13
        int u = q.front(); q.pop();
14
        order.push_back(u);
15
        for (int v : adj[u]) {
16
            if (--indeg[v] == 0) q.push(v);
17
        }
18
    }
19
    return order;
20
}
21
// Độ phức tạp: O(V + E)

KMP - Tìm kiếm chuỗi#

1
#include <vector>
2
#include <string>
3
using namespace std;
4

5
vector<int> kmp_prefix(const string& pattern) {
6
    int n = pattern.size();
7
    vector<int> pi(n, 0);
8
    for (int i = 1, j = 0; i < n; ++i) {
9
        while (j > 0 && pattern[i] != pattern[j]) j = pi[j-1];
10
        if (pattern[i] == pattern[j]) ++j;
11
        pi[i] = j;
12
    }
13
    return pi;
14
}
15

16
vector<int> kmp_search(const string& text, const string& pattern) {
17
    vector<int> pi = kmp_prefix(pattern), res;
18
    int n = text.size(), m = pattern.size();
19
    for (int i = 0, j = 0; i < n; ++i) {
20
        while (j > 0 && text[i] != pattern[j]) j = pi[j-1];
21
        if (text[i] == pattern[j]) ++j;
22
        if (j == m) {
23
            res.push_back(i - m + 1);
24
            j = pi[j-1];
25
        }
26
    }
27
    return res;
28
}
29
// Độ phức tạp: O(n + m)

Aho-Corasick - Tìm kiếm nhiều mẫu#

1
#include <vector>
2
#include <queue>
3
#include <string>
4
using namespace std;
5

6
struct ACNode {
7
    vector<ACNode*> children;
8
    ACNode* fail;
9
    vector<int> output;
10
    ACNode() : children(26, nullptr), fail(nullptr) {}
11
};
12

13
struct AhoCorasick {
14
    ACNode* root;
15
    AhoCorasick() : root(new ACNode()) {}
16
    void insert(const string& word, int id) {
17
        ACNode* node = root;
18
        for (char c : word) {
19
            int idx = c - 'a';
20
            if (!node->children[idx]) node->children[idx] = new ACNode();
21
            node = node->children[idx];
22
        }
23
        node->output.push_back(id);
24
    }
25
    void build() {
26
        queue<ACNode*> q;
27
        root->fail = root;
28
        for (int i = 0; i < 26; ++i) {
29
            if (root->children[i]) {
30
                root->children[i]->fail = root;
31
                q.push(root->children[i]);
32
            } else {
33
                root->children[i] = root;
34
            }
35
        }
36
        while (!q.empty()) {
37
            ACNode* node = q.front(); q.pop();
38
            for (int i = 0; i < 26; ++i) {
39
                if (node->children[i]) {
40
                    ACNode* f = node->fail;
41
                    while (!f->children[i]) f = f->fail;
42
                    node->children[i]->fail = f->children[i];
43
                    node->children[i]->output.insert(
44
                        node->children[i]->output.end(),
45
                        f->children[i]->output.begin(),
46
                        f->children[i]->output.end()
47
                    );
48
                    q.push(node->children[i]);
49
                }
50
            }
51
        }
52
    }
53
    // Hàm tìm kiếm trả về vị trí xuất hiện của các mẫu
54
    vector<pair<int, int>> search(const string& text) {
55
        vector<pair<int, int>> res;
56
        ACNode* node = root;
57
        for (int i = 0; i < text.size(); ++i) {
58
            int idx = text[i] - 'a';
59
            while (!node->children[idx]) node = node->fail;
60
            node = node->children[idx];
61
            for (int id : node->output) res.emplace_back(i, id);
62
        }
63
        return res;
64
    }
65
};
66
// Độ phức tạp: O(N + M + Z) với N: tổng độ dài mẫu, M: độ dài văn bản, Z: số lần khớp

Splay Tree#

1
#include <iostream>
2
using namespace std;
3

4
struct SplayNode {
5
    int key;
6
    SplayNode *left, *right, *parent;
7
    SplayNode(int k) : key(k), left(nullptr), right(nullptr), parent(nullptr) {}
8
};
9

10
void rotate(SplayNode*& root, SplayNode* x) {
11
    SplayNode* p = x->parent;
12
    if (!p) return;
13
    SplayNode* g = p->parent;
14
    if (p->left == x) {
15
        p->left = x->right;
16
        if (x->right) x->right->parent = p;
17
        x->right = p;
18
    } else {
19
        p->right = x->left;
20
        if (x->left) x->left->parent = p;
21
        x->left = p;
22
    }
23
    p->parent = x;
24
    x->parent = g;
25
    if (g) {
26
        if (g->left == p) g->left = x;
27
        else g->right = x;
28
    } else {
29
        root = x;
30
    }
31
}
32

33
void splay(SplayNode*& root, SplayNode* x) {
34
    while (x->parent) {
35
        SplayNode* p = x->parent;
36
        SplayNode* g = p->parent;
37
        if (!g) {
38
            rotate(root, x);
39
        } else if ((g->left == p) == (p->left == x)) {
40
            rotate(root, p);
41
            rotate(root, x);
42
        } else {
43
            rotate(root, x);
44
            rotate(root, x);
45
        }
46
    }
47
}
48
// Độ phức tạp trung bình: O(log n) cho mỗi thao tác

Segment Tree (Cây đoạn)#

1
#include <vector>
2
using namespace std;
3

4
struct SegmentTree {
5
    int n;
6
    vector<int> tree;
7
    SegmentTree(const vector<int>& a) {
8
        n = a.size();
9
        tree.resize(4 * n);
10
        build(a, 1, 0, n - 1);
11
    }
12
    void build(const vector<int>& a, int v, int l, int r) {
13
        if (l == r) tree[v] = a[l];
14
        else {
15
            int m = (l + r) / 2;
16
            build(a, v * 2, l, m);
17
            build(a, v * 2 + 1, m + 1, r);
18
            tree[v] = tree[v * 2] + tree[v * 2 + 1];
19
        }
20
    }
21
    int query(int v, int l, int r, int ql, int qr) {
22
        if (ql > r || qr < l) return 0;
23
        if (ql <= l && r <= qr) return tree[v];
24
        int m = (l + r) / 2;
25
        return query(v * 2, l, m, ql, qr) + query(v * 2 + 1, m + 1, r, ql, qr);
26
    }
27
    void update(int v, int l, int r, int pos, int val) {
28
        if (l == r) tree[v] = val;
29
        else {
30
            int m = (l + r) / 2;
31
            if (pos <= m) update(v * 2, l, m, pos, val);
32
            else update(v * 2 + 1, m + 1, r, pos, val);
33
            tree[v] = tree[v * 2] + tree[v * 2 + 1];
34
        }
35
    }
36
};
37
// Độ phức tạp: O(log n) cho mỗi truy vấn/cập nhật

Binary Tree (Cây nhị phân)#

1
template<typename T>
2
struct TreeNode {
3
    T data;
4
    TreeNode* left;
5
    TreeNode* right;
6

7
    TreeNode(const T& val) : data(val), left(nullptr), right(nullptr) {}
8
};
9

10
template<typename T>
11
class BinaryTree {
12
private:
13
    TreeNode<T>* root;
14

15
    void destroyTree(TreeNode<T>* node) {
16
        if (node) {
17
            destroyTree(node->left);
18
            destroyTree(node->right);
19
            delete node;
20
        }
21
    }
22

23
    void inorderTraversal(TreeNode<T>* node) const {
24
        if (node) {
25
            inorderTraversal(node->left);
26
            std::cout << node->data << " ";
27
            inorderTraversal(node->right);
28
        }
29
    }
30

31
    void preorderTraversal(TreeNode<T>* node) const {
32
        if (node) {
33
            std::cout << node->data << " ";
34
            preorderTraversal(node->left);
35
            preorderTraversal(node->right);
36
        }
37
    }
38

39
    void postorderTraversal(TreeNode<T>* node) const {
40
        if (node) {
41
            postorderTraversal(node->left);
42
            postorderTraversal(node->right);
43
            std::cout << node->data << " ";
44
        }
45
    }
46

47
public:
48
    BinaryTree() : root(nullptr) {}
49

50
    ~BinaryTree() {
51
        destroyTree(root);
52
    }
53

54
    void insert(const T& val) {
55
        root = insertNode(root, val);
56
    }
57

58
    TreeNode<T>* insertNode(TreeNode<T>* node, const T& val) {
59
        if (!node) {
60
            return new TreeNode<T>(val);
61
        }
62

63
        if (val < node->data) {
64
            node->left = insertNode(node->left, val);
65
        } else if (val > node->data) {
66
            node->right = insertNode(node->right, val);
67
        }
68

69
        return node;
70
    }
71

72
    void inorder() const {
73
        inorderTraversal(root);
74
        std::cout << std::endl;
75
    }
76

77
    void preorder() const {
78
        preorderTraversal(root);
79
        std::cout << std::endl;
80
    }
81

82
    void postorder() const {
83
        postorderTraversal(root);
84
        std::cout << std::endl;
85
    }
86
};
87
// Độ phức tạp: O(nlogn) với n là số nút

Linked List (Danh sách liên kết đơn)#

1
template<typename T>
2
struct ListNode {
3
    T data;
4
    ListNode* next;
5

6
    ListNode(const T& val) : data(val), next(nullptr) {}
7
};
8

9
template<typename T>
10
class LinkedList {
11
private:
12
    ListNode<T>* head;
13

14
public:
15
    LinkedList() : head(nullptr) {}
16

17
    ~LinkedList() {
18
        clear();
19
    }
20

21
    void insert(const T& val) {
22
        ListNode<T>* newNode = new ListNode<T>(val);
23
        newNode->next = head;
24
        head = newNode;
25
    }
26

27
    void remove(const T& val) {
28
        if (!head) return;
29

30
        if (head->data == val) {
31
            ListNode<T>* temp = head;
32
            head = head->next;
33
            delete temp;
34
            return;
35
        }
36

37
        ListNode<T>* current = head;
38
        while (current->next && current->next->data != val) {
39
            current = current->next;
40
        }
41

42
        if (current->next) {
43
            ListNode<T>* temp = current->next;
44
            current->next = current->next->next;
45
            delete temp;
46
        }
47
    }
48

49
    bool search(const T& val) const {
50
        ListNode<T>* current = head;
51
        while (current) {
52
            if (current->data == val) {
53
                return true;
54
            }
55
            current = current->next;
56
        }
57
        return false;
58
    }
59

60
    void clear() {
61
        while (head) {
62
            ListNode<T>* temp = head;
63
            head = head->next;
64
            delete temp;
65
        }
66
    }
67
};
68
// Độ phức tạp: O(n) với n là số node

Kết luận#

Những thuật toán cơ bản này là nền tảng quan trọng trong lập trình và khoa học máy tính. Việc hiểu rõ và thực hành các thuật toán này sẽ giúp bạn:

Tối ưu hóa code: Chọn thuật toán phù hợp cho từng bài toán
Phỏng vấn: Chuẩn bị tốt cho các cuộc phỏng vấn kỹ thuật
Tư duy logic: Phát triển khả năng giải quyết vấn đề
Nghiên cứu AI: Hiểu sâu các thuật toán machine learning

Lời khuyên:#

Thực hành thường xuyên: Code lại các thuật toán nhiều lần
Phân tích độ phức tạp: Hiểu rõ Big O notation
So sánh hiệu suất: Test với các bộ dữ liệu khác nhau
Áp dụng thực tế: Tìm hiểu cách sử dụng trong các framework

Hãy tiếp tục học tập và khám phá thêm các thuật toán nâng cao!