28 tài liệu đã gắn thẻ được gắn thẻ "thuat-toan"

Bellman-Ford xử lý cạnh âm và phát hiện chu trình âm O(VE); Floyd-Warshall tìm đường ngắn nhất mọi cặp O(V^3) bằng quy hoạch động.

Kỹ thuật tìm nhị phân trên không gian đáp án khi điều kiện kiểm tra đơn điệu, qua các bài kinh điển chia kẹo và tốc độ ăn chuối Koko.

Cây khung nhỏ nhất (MST) bằng Prim (heap mở rộng dần) và Kruskal (sắp cạnh + Union-Find).

Mẫu chia - giải - gộp; đếm nghịch thế, max-subarray, lũy thừa nhanh, liên hệ merge sort.

Dijkstra tìm đường đi ngắn nhất từ một nguồn trên đồ thị trọng số không âm, dùng heap, đạt O(E log V).

Dạng DP đơn giản nhất với bảng dp một chiều — leo cầu thang, House Robber, và dãy con tăng dài nhất (LIS).

Khi trạng thái cần hai chỉ số — dãy con chung dài nhất (LCS), khoảng cách chỉnh sửa (edit distance) và bài toán cái túi 0/1.

DP trên lưới 2D — đếm đường đi, tổng đường đi nhỏ nhất, và chuỗi con đối xứng dài nhất.

BFS duyệt đồ thị theo từng lớp bằng queue, tìm đường ngắn nhất theo số cạnh trên đồ thị không trọng số.

DFS lao sâu theo một nhánh rồi quay lui, dùng đệ quy hoặc stack; ứng dụng thành phần liên thông và phát hiện chu trình.

Heap sort dùng max-heap để liên tục lấy phần tử lớn nhất — O(n log n), sắp tại chỗ O(1) bộ nhớ, nhưng không ổn định.

Merge sort dùng chia để trị — cắt đôi, sắp từng nửa rồi trộn lại — đạt O(n log n) ổn định, đánh đổi bằng O(n) bộ nhớ.

Tính ổn định (stable) là gì, vì sao nó quan trọng, và bảng so sánh đầy đủ thời gian/bộ nhớ/ổn định của mọi thuật toán sắp xếp.

Khung tổng quát thử - đệ quy - hoàn tác; sinh hoán vị, tổ hợp, subsets, N-Queens và cắt tỉa (pruning).

Quick sort phân hoạch quanh một pivot — trung bình O(n log n), xấu nhất O(n^2) — và mẹo chọn pivot để né trường hợp xấu.

Quy hoạch động giải bài toán bằng cách lưu lại kết quả của các bài toán con gối nhau, biến đệ quy mũ thành tuyến tính.

Ba thuật toán sắp xếp đầu tiên — nổi bọt, chọn, chèn — đều O(n^2) nhưng dạy ta trực giác nền tảng về sắp xếp.

Counting, Radix và Bucket sort không so sánh phần tử với nhau — nhờ đó vượt giới hạn O(n log n), đạt O(n + k) khi khóa là số nguyên dải hẹp.

Sắp xếp tô-pô trên DAG bằng thuật toán Kahn (in-degree + queue) và bằng DFS; ứng dụng lịch học và biên dịch.

Tham lam chọn tối ưu cục bộ ở mỗi bước; khi nào đúng (lựa chọn tham lam + cấu trúc con tối ưu) và khi nào sai.

AND, OR, XOR, NOT, dịch bit và những mẹo kinh điển — kiểm tra chẵn lẻ, bật/tắt/đảo bit thứ k, đếm bit 1, dùng bitmask.

Định nghĩa thuật toán, năm tính chất bắt buộc, mô tả bằng pseudocode và sơ đồ khối, chạy debug từng bước qua ví dụ tìm số lớn nhất.

So khớp mẫu trong văn bản — từ cách ngây thơ O(nm) tới KMP với mảng prefix-function O(n+m) và Rabin-Karp với rolling hash.

Hiểu thuật toán tìm kiếm nhị phân qua hình động, code chạy trực tiếp, mẫu nhận diện và bài luyện tập.

Quét từng phần tử để tìm mục tiêu, độ phức tạp O(n), khi nào nên dùng và mẹo sentinel.

GCD bằng thuật toán Euclid, LCM, sàng Eratosthenes tìm số nguyên tố, và số học modular gồm lũy thừa mod nhanh.

Kỹ thuật cuộn mảng (rolling array) giảm bộ nhớ DP từ O(n·m) xuống O(m), chỉ giữ một hoặc hai hàng.

Union-Find quản lý các nhóm rời nhau với find và union; nén đường và hợp theo hạng cho gần O(1) khấu hao.