Các Thuật Toán Cơ Bản Trong Lập Trình Thi Đấu

Thuật toán Kosaraju (tìm thành phần liên thông mạnh) - O(3N+M)

Thuật sinh ước (sinh ước bằng thừa số nguyên tố) - O(NlogN+d)

Thuật toán Hamilton (tìm chu trình Hamilton) - O(N+M)

Thuật toán tính tổng đoạn- O(log3(N))

Thuật toán Sliding Window (cửa sổ trượt) - O(2N-K)

Kĩ thuật tiền tố và hậu tố (prefix sum và suffix sum) - O(N) / O(2N)

Tính tổ hợp không giai thừa (modulo và Không modulo) - O(K) và O(KlogMOD)

Thuật toán Sparse Table (truy vấn tổng L-R) - O(NlogN + log2(N))

Thuật toán Tarjan (tìm khớp và cầu) - O(N+M)

Thuật toán nhân ma trận Fibonacci - O(log(N))

Thuật toán đếm ước nhanh - O(N^⅓)

Thuật đếm ước/tổng các ước - O(√N)

Kiểm tra số nguyên tố (Miller Rabin) - O(K log(N))

Phân tích thừa số nguyên tố không tầm thường Pollrad's RHO - O(N^¼)

Thuật toán sàng nguyên tố (Eratosthenes) - O(NloglogN)

Phân tích thừa số nguyên tố - O(√NlogN)

Kiểm tra số nguyên tố - O(√N//6)

Thuật toán Convex Hull (Bao lồi) - O(Nlog(N))

Thuật toán Tìm kiếm nhị phân (có truy vấn) - O(T*log(N))

Thuật toán Kahn (kiểm chu trình) - O(N+M)

Thuật toán Kahn (Sort Topo) - O(N+M)

Thuật toán Kadane (mở rộng và có truy vấn) - O(T*N)

Thuật toán Floyd Warshall - O(N³)

Thuật toán BFS duyệt đường đi BFS - O(N+M)

Thuật toán DFS kiểm chu trình - O(N+M)

Thuật toán Dijkstra - O(N+M log(N))

Lũy thừa nhị phân - O(log2(N))