Trực quan hóa tương tác

Thuật toán

Chạy, tạm dừng, tua từng bước qua các thuật toán kinh điển — với mã nguồn thật ở nhiều ngôn ngữ, ngay trong trình duyệt.

50thuật toán

9nhóm

4ngôn ngữ

Bubble Sort

Duyệt qua danh sách nhiều lần, hoán đổi các cặp liền kề sai thứ tự để phần tử lớn nhất 'nổi' dần về cuối.

TB O(n²)Bộ nhớ O(1)

Selection Sort

Mỗi lượt tìm phần tử nhỏ nhất trong phần chưa sắp xếp rồi đưa lên đầu.

TB O(n²)Bộ nhớ O(1)

Insertion Sort

Xây dựng mảng đã sắp xếp từng phần tử một, chèn mỗi phần tử mới vào đúng vị trí trong đoạn đầu đã sắp.

TB O(n²)Bộ nhớ O(1)

Quick Sort

Chia để trị: chọn một pivot, phân hoạch các giá trị quanh nó, rồi đệ quy sắp xếp hai phía.

TB O(n log n)Bộ nhớ O(log n)

Merge Sort

Chia để trị: chia đôi mảng, sắp xếp từng nửa, rồi trộn hai nửa đã sắp lại với nhau.

TB O(n log n)Bộ nhớ O(n)

Heap Sort

Xây max-heap rồi liên tục đưa gốc (lớn nhất) về cuối và khôi phục heap — tại chỗ và O(n log n) trong mọi trường hợp.

TB O(n log n)Bộ nhớ O(1)

Shell Sort

Bản tổng quát của insertion sort theo 'bước nhảy': sắp các phần tử cách xa trước, thu nhỏ dần bước nhảy đến khi thành một lượt insertion sort thường.

TB O(n^1.25)Bộ nhớ O(1)

Cocktail Shaker Sort

Bubble sort hai chiều: mỗi vòng đẩy phần tử lớn nhất sang phải rồi nhỏ nhất sang trái, thu hẹp dần từ hai đầu.

TB O(n²)Bộ nhớ O(1)

Quicksort Ba Chiều

Phân hoạch 'quốc kỳ Hà Lan' của Dijkstra chia thành <, = và > chốt trong một lượt, nên các khóa trùng nhau xong ngay.

TB O(n log n)Bộ nhớ O(log n)

Counting Sort

Sắp xếp mà không so sánh lần nào bằng cách đếm số lần xuất hiện của mỗi khóa, rồi ghi lại theo thứ tự — O(n + k).

TB O(n + k)Bộ nhớ O(k)

Radix Sort

Sắp xếp từng chữ số một, từ thấp tới cao, mỗi chữ số một lượt chia thùng ổn định — O(d · n), không so sánh.

TB O(d · (n + b))Bộ nhớ O(n + b)

Tìm kiếm tuyến tính

Kiểm tra lần lượt từng phần tử cho đến khi tìm thấy hoặc hết mảng. Hoạt động với mọi mảng, dù có sắp xếp hay không.

TB O(n)Bộ nhớ O(1)

Tìm kiếm nhị phân

Trên mảng đã sắp xếp, liên tục chia đôi vùng tìm bằng cách so sánh phần tử giữa với target — O(log n).

TB O(log n)Bộ nhớ O(1)

Tìm kiếm nhảy bước

Trên mảng đã sắp xếp, nhảy theo khối cố định √n cho đến khi vượt qua target, rồi quét tuyến tính trong khối cuối.

TB O(√n)Bộ nhớ O(1)

Tìm kiếm nội suy

Giống tìm kiếm nhị phân nhưng ước lượng vị trí dò từ giá trị target — gần O(log log n) trên dữ liệu phân bố đều.

TB O(log log n)Bộ nhớ O(1)

Tìm kiếm lũy thừa

Nhân đôi cận chỉ số cho đến khi vượt target, rồi tìm nhị phân trong khoảng đó — rất hợp cho dữ liệu sắp xếp rất lớn hoặc không biết kích thước.

TB O(log n)Bộ nhớ O(1)

Ternary Search

Chia khoảng thành ba phần với hai điểm dò mỗi vòng — cùng bậc với binary search, nhưng nhiều phép so sánh hơn.

TB O(log₃ n)Bộ nhớ O(1)

Fibonacci Search

Thu hẹp khoảng theo các số Fibonacci thay vì chia đôi, nên mọi điểm dò chỉ cần phép cộng — không có phép chia.

TB O(log n)Bộ nhớ O(1)

Tìm kiếm theo chiều rộng (BFS)

Lan tỏa theo từng vòng từ điểm bắt đầu, đảm bảo đường đi ít bước nhất trên lưới không trọng số.

TB O(V + E)Bộ nhớ O(V)

Tìm kiếm theo chiều sâu (DFS)

Đi sâu hết mức theo một nhánh rồi mới quay lui. Tìm được đường đi, nhưng không nhất thiết ngắn nhất.

TB O(V + E)Bộ nhớ O(V)

Thuật toán Dijkstra

Luôn mở rộng nút gần nhất bằng hàng đợi ưu tiên, cho đường đi ngắn nhất kể cả khi các ô có chi phí khác nhau (trọng số).

TB O(E log V)Bộ nhớ O(V)

Tìm kiếm A*

Giống Dijkstra nhưng dùng hàm heuristic kéo hướng tìm về đích — nên duyệt ít ô hơn nhiều mà vẫn cho đường ngắn nhất.

TB O(E log V)Bộ nhớ O(V)

Tìm kiếm tham lam tốt nhất

Luôn mở rộng nút trông gần đích nhất chỉ dựa trên heuristic. Rất nhanh và nhắm hướng, nhưng đường đi không đảm bảo ngắn nhất.

TB O(E log V)Bộ nhớ O(V)

Dãy con chung dài nhất (LCS)

Điền bảng với dp[i][j] là độ dài LCS của i và j ký tự đầu — mỗi ô suy ra từ ô chéo, trên hoặc trái.

TB O(m·n)Bộ nhớ O(m·n)

Khoảng cách chỉnh sửa

Khoảng cách Levenshtein: số phép chèn/xóa/thay tối thiểu để biến chuỗi này thành chuỗi kia, dựng từng ô một.

TB O(m·n)Bộ nhớ O(m·n)

Chuỗi Con Chung Dài Nhất

Cùng bảng với LCS nhưng đổi một quy tắc: không khớp thì ô về 0, vì chuỗi con phải liên tiếp.

TB O(m·n)Bộ nhớ O(m·n)

Knapsack 0/1

Xếp tập vật phẩm giá trị nhất trong giới hạn khối lượng. Mỗi ô chỉ hỏi một câu: bỏ qua vật này, hay lấy nó?

TB O(n·W)Bộ nhớ O(n·W)

Đổi Tiền (QHĐ)

Số đồng ít nhất cho một số tiền — và cái bảng chứng minh rằng đáp án greedy có thể sai.

TB O(m·A)Bộ nhớ O(m·A)

Duyệt Inorder

Duyệt Trái → Gốc → Phải. Trên cây tìm kiếm nhị phân, cho ra các giá trị theo thứ tự tăng dần.

TB O(n)Bộ nhớ O(n)

Duyệt Preorder

Duyệt Gốc → Trái → Phải. Hữu ích để sao chép cây hoặc tuần tự hóa cấu trúc.

TB O(n)Bộ nhớ O(n)

Duyệt Postorder

Duyệt Trái → Phải → Gốc. Con được xử lý trước cha — tiện để xóa hoặc tính giá trị cây.

TB O(n)Bộ nhớ O(n)

Duyệt theo tầng

Theo chiều rộng: duyệt cây từng tầng một, trái sang phải, dùng hàng đợi.

TB O(n)Bộ nhớ O(n)

Duyệt Zigzag Theo Tầng

Theo chiều rộng nhưng đảo chiều: hàng đầu trái sang phải, hàng sau phải sang trái, xoắn dần xuống dưới.

TB O(n)Bộ nhớ O(n)

Tìm kiếm trên BST

Đi xuống từ gốc, rẽ trái hoặc phải bằng cách so sánh target với từng nút — O(log n) trên cây cân bằng.

TB O(log n)Bộ nhớ O(1)

N Quân Hậu

Đặt N quân hậu lên bàn cờ N×N sao cho không quân nào cùng hàng, cột hay đường chéo — thử từng cột theo hàng và quay lui khi xung đột.

TB O(n!)Bộ nhớ O(n)

Tháp Hà Nội

Bài toán đệ quy kinh điển: chuyển chồng đĩa sang cọc khác, không bao giờ đặt đĩa lớn lên đĩa nhỏ. Giải trong 2ⁿ − 1 bước.

TB O(2ⁿ)Bộ nhớ O(n)

Giải Sudoku

Quay lui ở dạng dễ nhận ra nhất: thử một số, đệ quy, và xóa nó ngay khi nhánh đó chết.

TB O(9^m)Bộ nhớ O(m)

Hai con trỏ

Trên mảng đã sắp, hai con trỏ xuất phát từ hai đầu và tiến vào giữa — tăng hoặc giảm tổng — để tìm cặp có tổng cho trước trong O(n).

TB O(n)Bộ nhớ O(1)

Cửa sổ trượt

Duy trì tổng của một cửa sổ kích thước cố định khi trượt dọc mảng — cộng phần tử vào và bỏ phần tử ra — để tìm tổng cửa sổ lớn nhất trong O(n).

TB O(n)Bộ nhớ O(1)

Thuật Toán Kadane

Tổng lớn nhất của một dãy con liên tiếp, trong một lượt: khi tổng đang chạy hóa âm thì bỏ nó và bắt đầu lại.

TB O(n)Bộ nhớ O(1)

Bầu Chọn Đa Số Boyer–Moore

Tìm giá trị chiếm hơn một nửa mảng chỉ với một bộ đếm và không cần bộ nhớ phụ — các giá trị khác nhau tự triệt tiêu.

TB O(n)Bộ nhớ O(1)

Đệ quy

Một hàm tự gọi chính nó trên đầu vào nhỏ hơn cho tới trường hợp cơ sở. Fibonacci cho thấy cây gọi phân nhánh mọc ra rồi thu về — và vì sao đệ quy ngây thơ lặp lại công việc.

TB O(φⁿ)Bộ nhớ O(n)

Chia để trị

Chia bài toán thành hai nửa, giải đệ quy từng nửa rồi kết hợp kết quả. Ở đây là tìm phần tử lớn nhất của mảng — cùng khuôn mẫu tạo nên Merge Sort và Quick Sort.

TB O(n)Bộ nhớ O(log n)

Ghi nhớ (Memoization)

Lưu lại mỗi kết quả đệ quy ngay lần tính đầu tiên, nên các bài toán con lặp lại trả về tức thì. Cùng cây fib nhưng co từ hàm mũ xuống tuyến tính.

TB O(n)Bộ nhớ O(n)

Nhánh cận

Duyệt cây quyết định của bài toán ba lô 0/1, nhưng tính một cận trên lạc quan tại mỗi nút và cắt bỏ mọi nhánh không thể vượt lời giải tốt nhất đã tìm được.

TB O(2ⁿ)Bộ nhớ O(n)

Tham lam (Đổi tiền)

Trả một số tiền bằng cách liên tục lấy đồng xu lớn nhất còn vừa. Nhanh và tối ưu với hệ tiền chuẩn — nhưng demo còn cho thấy bộ xu khiến tham lam thất bại.

TB O(n log n)Bộ nhớ O(1)

Union-Find (DSU)

Theo dõi việc chia các phần tử thành các tập rời rạc, với thao tác hợp và truy vấn liên thông gần như hằng số nhờ hợp-theo-hạng và nén đường.

TB O(α(n))Bộ nhớ O(n)

Heap (Đống nhị phân)

Một cây nhị phân đầy đủ lưu trong mảng, trong đó mỗi nút cha luôn lớn hơn các con. Chèn thì đẩy lên, lấy-max thì đẩy xuống — đều O(log n).

TB O(log n)Bộ nhớ O(n)

Trie (Cây tiền tố)

Một cây khóa theo ký tự, các từ chung tiền tố dùng chung đường đi. Chèn và tra cứu đều chạy O(L) theo độ dài từ — không phụ thuộc số từ đã lưu.

TB O(L)Bộ nhớ O(N·L)

Cây phân đoạn

Một cây nhị phân lưu tổng hợp theo đoạn (ở đây là tổng), trả lời mọi truy vấn khoảng trong O(log n) bằng cách gộp vài nút phủ thay vì quét cả mảng.

TB O(log n)Bộ nhớ O(n)

Đang tải…

Trực quan hóa tương tác

Thuật toán

Chạy, tạm dừng, tua từng bước qua các thuật toán kinh điển — với mã nguồn thật ở nhiều ngôn ngữ, ngay trong trình duyệt.

50thuật toán

9nhóm

4ngôn ngữ

Bubble Sort

Duyệt qua danh sách nhiều lần, hoán đổi các cặp liền kề sai thứ tự để phần tử lớn nhất 'nổi' dần về cuối.

TB O(n²)Bộ nhớ O(1)

Selection Sort

Mỗi lượt tìm phần tử nhỏ nhất trong phần chưa sắp xếp rồi đưa lên đầu.

TB O(n²)Bộ nhớ O(1)

Insertion Sort

Xây dựng mảng đã sắp xếp từng phần tử một, chèn mỗi phần tử mới vào đúng vị trí trong đoạn đầu đã sắp.

TB O(n²)Bộ nhớ O(1)

Quick Sort

Chia để trị: chọn một pivot, phân hoạch các giá trị quanh nó, rồi đệ quy sắp xếp hai phía.

TB O(n log n)Bộ nhớ O(log n)

Merge Sort

Chia để trị: chia đôi mảng, sắp xếp từng nửa, rồi trộn hai nửa đã sắp lại với nhau.

TB O(n log n)Bộ nhớ O(n)

Heap Sort

Xây max-heap rồi liên tục đưa gốc (lớn nhất) về cuối và khôi phục heap — tại chỗ và O(n log n) trong mọi trường hợp.

TB O(n log n)Bộ nhớ O(1)

Shell Sort

Bản tổng quát của insertion sort theo 'bước nhảy': sắp các phần tử cách xa trước, thu nhỏ dần bước nhảy đến khi thành một lượt insertion sort thường.

TB O(n^1.25)Bộ nhớ O(1)

Cocktail Shaker Sort

Bubble sort hai chiều: mỗi vòng đẩy phần tử lớn nhất sang phải rồi nhỏ nhất sang trái, thu hẹp dần từ hai đầu.

TB O(n²)Bộ nhớ O(1)

Quicksort Ba Chiều

Phân hoạch 'quốc kỳ Hà Lan' của Dijkstra chia thành <, = và > chốt trong một lượt, nên các khóa trùng nhau xong ngay.

TB O(n log n)Bộ nhớ O(log n)

Counting Sort

Sắp xếp mà không so sánh lần nào bằng cách đếm số lần xuất hiện của mỗi khóa, rồi ghi lại theo thứ tự — O(n + k).

TB O(n + k)Bộ nhớ O(k)

Radix Sort

Sắp xếp từng chữ số một, từ thấp tới cao, mỗi chữ số một lượt chia thùng ổn định — O(d · n), không so sánh.

TB O(d · (n + b))Bộ nhớ O(n + b)

Tìm kiếm tuyến tính

Kiểm tra lần lượt từng phần tử cho đến khi tìm thấy hoặc hết mảng. Hoạt động với mọi mảng, dù có sắp xếp hay không.

TB O(n)Bộ nhớ O(1)

Tìm kiếm nhị phân

Trên mảng đã sắp xếp, liên tục chia đôi vùng tìm bằng cách so sánh phần tử giữa với target — O(log n).

TB O(log n)Bộ nhớ O(1)

Tìm kiếm nhảy bước

Trên mảng đã sắp xếp, nhảy theo khối cố định √n cho đến khi vượt qua target, rồi quét tuyến tính trong khối cuối.

TB O(√n)Bộ nhớ O(1)

Tìm kiếm nội suy

Giống tìm kiếm nhị phân nhưng ước lượng vị trí dò từ giá trị target — gần O(log log n) trên dữ liệu phân bố đều.

TB O(log log n)Bộ nhớ O(1)

Tìm kiếm lũy thừa

Nhân đôi cận chỉ số cho đến khi vượt target, rồi tìm nhị phân trong khoảng đó — rất hợp cho dữ liệu sắp xếp rất lớn hoặc không biết kích thước.

TB O(log n)Bộ nhớ O(1)

Ternary Search

Chia khoảng thành ba phần với hai điểm dò mỗi vòng — cùng bậc với binary search, nhưng nhiều phép so sánh hơn.

TB O(log₃ n)Bộ nhớ O(1)

Fibonacci Search

Thu hẹp khoảng theo các số Fibonacci thay vì chia đôi, nên mọi điểm dò chỉ cần phép cộng — không có phép chia.

TB O(log n)Bộ nhớ O(1)

Tìm kiếm theo chiều rộng (BFS)

Lan tỏa theo từng vòng từ điểm bắt đầu, đảm bảo đường đi ít bước nhất trên lưới không trọng số.

TB O(V + E)Bộ nhớ O(V)

Tìm kiếm theo chiều sâu (DFS)

Đi sâu hết mức theo một nhánh rồi mới quay lui. Tìm được đường đi, nhưng không nhất thiết ngắn nhất.

TB O(V + E)Bộ nhớ O(V)

Thuật toán Dijkstra

Luôn mở rộng nút gần nhất bằng hàng đợi ưu tiên, cho đường đi ngắn nhất kể cả khi các ô có chi phí khác nhau (trọng số).

TB O(E log V)Bộ nhớ O(V)

Tìm kiếm A*

Giống Dijkstra nhưng dùng hàm heuristic kéo hướng tìm về đích — nên duyệt ít ô hơn nhiều mà vẫn cho đường ngắn nhất.

TB O(E log V)Bộ nhớ O(V)

Tìm kiếm tham lam tốt nhất

Luôn mở rộng nút trông gần đích nhất chỉ dựa trên heuristic. Rất nhanh và nhắm hướng, nhưng đường đi không đảm bảo ngắn nhất.

TB O(E log V)Bộ nhớ O(V)

Dãy con chung dài nhất (LCS)

Điền bảng với dp[i][j] là độ dài LCS của i và j ký tự đầu — mỗi ô suy ra từ ô chéo, trên hoặc trái.

TB O(m·n)Bộ nhớ O(m·n)

Khoảng cách chỉnh sửa

Khoảng cách Levenshtein: số phép chèn/xóa/thay tối thiểu để biến chuỗi này thành chuỗi kia, dựng từng ô một.

TB O(m·n)Bộ nhớ O(m·n)

Chuỗi Con Chung Dài Nhất

Cùng bảng với LCS nhưng đổi một quy tắc: không khớp thì ô về 0, vì chuỗi con phải liên tiếp.

TB O(m·n)Bộ nhớ O(m·n)

Knapsack 0/1

Xếp tập vật phẩm giá trị nhất trong giới hạn khối lượng. Mỗi ô chỉ hỏi một câu: bỏ qua vật này, hay lấy nó?

TB O(n·W)Bộ nhớ O(n·W)

Đổi Tiền (QHĐ)

Số đồng ít nhất cho một số tiền — và cái bảng chứng minh rằng đáp án greedy có thể sai.

TB O(m·A)Bộ nhớ O(m·A)

Duyệt Inorder

Duyệt Trái → Gốc → Phải. Trên cây tìm kiếm nhị phân, cho ra các giá trị theo thứ tự tăng dần.

TB O(n)Bộ nhớ O(n)

Duyệt Preorder

Duyệt Gốc → Trái → Phải. Hữu ích để sao chép cây hoặc tuần tự hóa cấu trúc.

TB O(n)Bộ nhớ O(n)

Duyệt Postorder

Duyệt Trái → Phải → Gốc. Con được xử lý trước cha — tiện để xóa hoặc tính giá trị cây.

TB O(n)Bộ nhớ O(n)

Duyệt theo tầng

Theo chiều rộng: duyệt cây từng tầng một, trái sang phải, dùng hàng đợi.

TB O(n)Bộ nhớ O(n)

Duyệt Zigzag Theo Tầng

Theo chiều rộng nhưng đảo chiều: hàng đầu trái sang phải, hàng sau phải sang trái, xoắn dần xuống dưới.

TB O(n)Bộ nhớ O(n)

Tìm kiếm trên BST

Đi xuống từ gốc, rẽ trái hoặc phải bằng cách so sánh target với từng nút — O(log n) trên cây cân bằng.

TB O(log n)Bộ nhớ O(1)

N Quân Hậu

Đặt N quân hậu lên bàn cờ N×N sao cho không quân nào cùng hàng, cột hay đường chéo — thử từng cột theo hàng và quay lui khi xung đột.

TB O(n!)Bộ nhớ O(n)

Tháp Hà Nội

Bài toán đệ quy kinh điển: chuyển chồng đĩa sang cọc khác, không bao giờ đặt đĩa lớn lên đĩa nhỏ. Giải trong 2ⁿ − 1 bước.

TB O(2ⁿ)Bộ nhớ O(n)

Giải Sudoku

Quay lui ở dạng dễ nhận ra nhất: thử một số, đệ quy, và xóa nó ngay khi nhánh đó chết.

TB O(9^m)Bộ nhớ O(m)

Hai con trỏ

Trên mảng đã sắp, hai con trỏ xuất phát từ hai đầu và tiến vào giữa — tăng hoặc giảm tổng — để tìm cặp có tổng cho trước trong O(n).

TB O(n)Bộ nhớ O(1)

Cửa sổ trượt

TB O(n)Bộ nhớ O(1)

Thuật Toán Kadane

Tổng lớn nhất của một dãy con liên tiếp, trong một lượt: khi tổng đang chạy hóa âm thì bỏ nó và bắt đầu lại.

TB O(n)Bộ nhớ O(1)

Bầu Chọn Đa Số Boyer–Moore

Tìm giá trị chiếm hơn một nửa mảng chỉ với một bộ đếm và không cần bộ nhớ phụ — các giá trị khác nhau tự triệt tiêu.

TB O(n)Bộ nhớ O(1)

Đệ quy

TB O(φⁿ)Bộ nhớ O(n)

Chia để trị

TB O(n)Bộ nhớ O(log n)

Ghi nhớ (Memoization)

Lưu lại mỗi kết quả đệ quy ngay lần tính đầu tiên, nên các bài toán con lặp lại trả về tức thì. Cùng cây fib nhưng co từ hàm mũ xuống tuyến tính.

TB O(n)Bộ nhớ O(n)

Nhánh cận

TB O(2ⁿ)Bộ nhớ O(n)

Tham lam (Đổi tiền)

TB O(n log n)Bộ nhớ O(1)

Union-Find (DSU)

Theo dõi việc chia các phần tử thành các tập rời rạc, với thao tác hợp và truy vấn liên thông gần như hằng số nhờ hợp-theo-hạng và nén đường.

TB O(α(n))Bộ nhớ O(n)

Heap (Đống nhị phân)

Một cây nhị phân đầy đủ lưu trong mảng, trong đó mỗi nút cha luôn lớn hơn các con. Chèn thì đẩy lên, lấy-max thì đẩy xuống — đều O(log n).

TB O(log n)Bộ nhớ O(n)

Trie (Cây tiền tố)

Một cây khóa theo ký tự, các từ chung tiền tố dùng chung đường đi. Chèn và tra cứu đều chạy O(L) theo độ dài từ — không phụ thuộc số từ đã lưu.

TB O(L)Bộ nhớ O(N·L)

Cây phân đoạn

Một cây nhị phân lưu tổng hợp theo đoạn (ở đây là tổng), trả lời mọi truy vấn khoảng trong O(log n) bằng cách gộp vài nút phủ thay vì quét cả mảng.

TB O(log n)Bộ nhớ O(n)