Là một tập hợp hữu hạn các bước rõ ràng, xác định và có thứ tự, dùng để giải quyết một bài toán hoặc thực hiện một nhiệm vụ cụ thể, biến dữ liệu đầu vào thành kết quả đầu ra.

Là một chương trình máy tính được viết bằng ngôn ngữ lập trình.

Là thiết bị phần cứng dùng để xử lý dữ liệu.

Là cách tổ chức dữ liệu trong bộ nhớ máy tính.

Vì thuật toán cần đảm bảo quá trình thực hiện sẽ kết thúc, cho ra kết quả xác định, có thể triển khai trên máy tính và tránh vòng lặp vô hạn gây treo chương trình.

Vì thuật toán phải chạy càng lâu càng tốt để xử lý nhiều dữ liệu.

Vì máy tính chỉ xử lý được số lượng bước vô hạn.

Vì thuật toán không cần kết quả đầu ra.

So sánh giá trị cần tìm với từng phần tử từ đầu đến cuối danh sách; nếu tìm thấy thì kết thúc. Thuật toán thường dùng cho mảng chưa sắp xếp, dữ liệu nhỏ và các bài toán đơn giản.

Chia mảng thành hai phần bằng nhau rồi tìm kiếm dệ quy trong mỗi phần.

Sắp xếp dữ liệu trước khi tìm kiếm để tăng tốc độ xử lý.

Chỉ áp dụng cho các mảng đã được sắp xếp tăng dần.

Trả về một giá trị đặc biệt (thường là $$-1$$ ) để biểu thị rằng phần tử không tồn tại trong tập dữ liệu, giúp phân biệt với các chỉ số hợp lệ.

Trả về phần tử cuối cùng của mảng.

Trả về giá trị $$0$$ .

Tự động thêm phần tử cần tìm vào mảng.

Trường hợp tốt nhất: thuật toán chạy nhanh nhất, ít bước nhất. Trường hợp xấu nhất: thuật toán chạy lâu nhất, nhiều bước nhất. Trường hợp trung bình: thời gian chạy kỳ vọng trung bình của thuật toán.

Tốt nhất: dữ liệu lớn nhất. Xấu nhất: dữ liệu nhỏ nhất. Trung bình: dữ liệu ngẫu nhiên.

Tốt nhất: luôn chạy trong thời gian hằng số. Xấu nhất: không bao giờ kết thúc. Trung bình: không xác định.

Chỉ tồn tại trường hợp xấu nhất; không có trường hợp tốt nhất và trung bình.

Vì thuật toán cung cấp một quy trình rõ ràng, có hệ thống và hữu hạn để biến dữ liệu đầu vào thành kết quả mong muốn.

Vì thuật toán luôn chạy nhanh nhất.

Vì thuật toán không cần dữ liệu đầu vào.

Vì thuật toán chỉ dùng cho máy tính mạnh.

Có tính xác định, tuần tự, đảm bảo kết thúc và có thể áp dụng cho nhiều trường hợp.

Không cần kết thúc.

Phụ thuộc vào máy tính.

Chỉ áp dụng cho một trường hợp duy nhất.

Thường tồn tại sự đánh đổi giữa thời gian chạy và lượng bộ nhớ sử dụng.

Luôn giống nhau.

Không liên quan gì đến nhau.

Chỉ xét một trong hai.

Sử dụng bảng băm (Hash Table) để đạt thời gian tìm kiếm trung bình $$O(1)$$ nhưng tốn bộ nhớ $$O(n)$$ .

Tìm kiếm tuyến tính trong mảng.

Bubble Sort.

Insertion Sort.

Vì thuật toán cho kết quả sai thì dù nhanh hay tối ưu đến đâu cũng vô nghĩa.

Vì giúp code ngắn hơn.

Vì giúp tiết kiệm bộ nhớ.

Vì dễ lập trình hơn.

Đúng → Chính xác → Hiệu quả → Tối ưu

Tối ưu → Đúng → Hiệu quả

Nhanh → Ít bộ nhớ → Đúng

Hiệu quả → Tối ưu → Đúng

Dễ mơ hồ, khó kiểm tra tính chính xác và không thể thực thi trực tiếp.

Khó đọc.

Phụ thuộc ngôn ngữ lập trình.

Không mô tả được thuật toán.

Giả mã (Pseudocode) vì rõ ràng, logic và dễ chuyển sang code

Ngôn ngữ tự nhiên

Lưu đồ

Ngôn ngữ lập trình

Vì thời gian chạy phụ thuộc vào dữ liệu đầu vào, môi trường và độ phức tạp thuật toán.

Vì mili giây không chính xác.

Vì thuật toán A luôn tốt hơn.

Vì thuật toán B chậm hơn.

Thời gian thực thi không phụ thuộc vào kích thước dữ liệu đầu vào.

Chỉ áp dụng cho dữ liệu nhỏ.

Luôn dùng nhiều bộ nhớ.

Chỉ dùng cho sắp xếp.

Thuật toán tìm kiếm nhị phân

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

Bubble Sort

Insertion Sort

Thời gian thực thi tăng tuyến tính theo số phần tử đầu vào

Thời gian tăng theo cấp số nhân

Không phụ thuộc vào dữ liệu

Giảm một nửa sau mỗi bước

Có hai vòng lặp lồng nhau, số bước xử lý xấp xỉ $$n \times n$$

Chỉ có một vòng lặp

Luôn chạy nhanh

Không phụ thuộc dữ liệu

Vì mỗi bước loại bỏ được một nửa dữ liệu cần tìm

Vì không cần sắp xếp dữ liệu

Vì dùng nhiều bộ nhớ

Vì luôn tìm thấy kết quả

Lưu và tái sử dụng kết quả bài toán con để tránh tính toán lặp

Không dùng bộ nhớ

Không dùng đệ quy

Không cần điều kiện dừng

Độ phức tạp rất lớn, không phù hợp với dữ liệu lớn

Khó cài đặt

Không tìm được lời giải

Không chính xác

Có điều kiện dừng rõ ràng

Có nhiều vòng lặp

Không dùng bộ nhớ

Không gọi lại chính nó

Giải cùng một bài toán nhưng hiệu quả hơn về thời gian và/hoặc bộ nhớ

Làm thuật toán phức tạp hơn

Làm code dài hơn

Chỉ giảm bộ nhớ

Vì Quick Sort có độ phức tạp trung bình $$O(n\,\log n)$$

Vì Bubble Sort không sắp xếp được

Vì Quick Sort không dùng đệ quy

Vì Bubble Sort luôn chậm

Vì trong trường hợp xấu nhất phải duyệt qua toàn bộ $$n$$ phần tử

Vì luôn chia đôi dữ liệu

Vì dùng đệ quy

Vì cần sắp xếp trước

Vì mỗi lời gọi sinh ra hai lời gọi con và nhiều giá trị bị tính lặp

Vì không có điều kiện dừng

Vì dùng mảng

Vì không dùng bộ nhớ

Chia bài toán thành các bài toán con, giải độc lập và kết hợp kết quả

Giải trực tiếp bài toán lớn

Thử tất cả các khả năng

Không dùng đệ quy

Khi phần tử không tồn tại hoặc nằm ở vị trí cuối cùng của mảng

Khi phần tử ở đầu mảng

Khi mảng đã sắp xếp

Khi dữ liệu nhỏ

Vì làm mảng con bị chia mất cân bằng, phá vỡ lợi thế chia để trị

Vì làm thuật toán dừng sớm

Vì giảm số phép so sánh

Vì tăng bộ nhớ sử dụng

Chia mảng thành các mảng con, sắp xếp rồi trộn các mảng con đã sắp xếp

So sánh từng cặp phần tử liền kề

Chọn phần tử nhỏ nhất đưa lên đầu

Chèn phần tử vào vị trí thích hợp

Sắp xếp chèn với khoảng cách giảm dần, thuộc sắp xếp nội bộ

Sắp xếp đổi chỗ trực tiếp

Sắp xếp dựa trên heap

Sắp xếp ngoài

Chia mảng thành hai phần nhỏ hơn và lớn hơn pivot

Gộp các mảng con

So sánh các phần tử kề nhau

Xây dựng heap

Mảng được sắp tăng hoặc giảm hoàn chỉnh

Mảng chỉ sắp xếp một phần

Mảng giữ nguyên thứ tự ban đầu

Mảng đảo ngược

$$O(n^2)$$

$$O(n\,\log n)$$

$$O(n)$$

$$O(\log n)$$

Thời gian chạy tốn với dữ liệu lớn

Tốn nhiều bộ nhớ

Khó cài đặt

Không xác định kết quả

Sắp xếp dữ liệu không đủ chứa trong bộ nhớ chính

Sắp xếp dữ liệu trong RAM

Sắp xếp mảng nhỏ

Sắp xếp tại chỗ

Khi dữ liệu rất lớn vượt quá bộ nhớ

Khi dữ liệu nhỏ

Khi mảng đã sắp xếp

Khi cần tốc độ cao

Heap

Stack

Queue

List

Ở gốc heap

Ở lá trái

Ở lá phải

Ở giữa mảng

Vì phải duyệt từng phần tử

Vì cần mảng sắp xếp

Vì dùng đệ quy

Vì dùng nhiều bộ nhớ

Giảm không gian tìm kiếm sau mỗi bước

Duyệt tuần tự

So sánh tất cả phần tử

Không cần sắp xếp

Thời gian chạy tăng tuyến tính

Không tìm được kết quả

Tốn nhiều bộ nhớ

Khó cài đặt

Khi cần minh họa đệ quy, dữ liệu nhỏ

Khi dữ liệu lớn

Khi cần tốc độ cao

Khi mảng đã sắp xếp

Lần gọi thứ 4

Lần gọi thứ 2

Lần gọi thứ 6

Lần gọi thứ 1

Sau lần gọi cuối cùng

Sau lần gọi đầu

Ngay khi so sánh lần 2

Không bao giờ

$$O(1)$$

$$O(n)$$

$$O(\log n)$$

$$O(n^2)$$

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

Tìm kiếm nhị phân

Code ngắn gọn, dễ hiểu

Chạy nhanh hơn

Ít dùng bộ nhớ

Không cần điều kiện dừng

Phải kiểm tra từng phần tử

Cần sắp xếp mảng

Dùng đệ quy

Dùng nhiều biến

Dữ liệu nhỏ, chưa sắp xếp

Dữ liệu rất lớn

Yêu cầu tốc độ cao

Mảng đã sắp xếp

Tìm tuyến tính trong phạm vi đó

Tìm nhị phân

Tìm toàn bộ mảng

Sắp xếp lại mảng

Khi dữ liệu phân bố đều

Khi dữ liệu ngẫu nhiên

Khi mảng nhỏ

Khi không sắp xếp

Phần tử nằm ở vị trí đầu

Phần tử ở cuối

Phần tử không tồn tại

Mảng rộng

$$O(n)$$

$$O(1)$$

$$O(\log n)$$

$$O(n^2)$$

Tốn chi phí gọi hàm

Duyệt ít phần tử

Không có điều kiện dừng

Phải sắp xếp mảng

Tốn nhiều bộ nhớ hơn

Ít bộ nhớ hơn

Bằng nhau

Không dùng bộ nhớ

$$O(n)$$

$$O(1)$$

$$O(\log n)$$

$$O(n^2)$$

Insertion Sort

Merge Sort

Heap Sort

Quick Sort

Chia để trị

Tham lam

Quy hoạch động

Vét cạn

Không dùng đệ quy

Tốn nhiều bộ nhớ hơn

Chậm hơn

Không ổn định

Phân vùng hiệu quả

Không cần so sánh

Không dùng đệ quy

Luôn $$O(n)$$

Ít hoán đổi

Chạy rất nhanh

Ổn định

$$O(n \log n)$$

Phụ thuộc thứ tự dữ liệu

Luôn bằng $$N$$

Luôn bằng $$N^2$$

Không xác định

So sánh và hoán đổi cục bộ

Dùng heap

Chia để trị

Không so sánh

for và while

do while

switch

goto

Ít phép so sánh và dịch chuyển

Không dùng vòng lặp

Không cần bộ nhớ

Không cần điều kiện

$$O(n)$$ và $$O(n^2)$$

$$O(\log n)$$ và $$O(n)$$

$$O(n^2)$$ và $$O(n^2)$$

$$O(1)$$ và $$O(n)$$

Mảng đảo ngược

Mảng đã sắp xếp

Mảng rỗng

Mảng 1 phần tử

Insertion Sort

Bubble Sort thường

Selection Sort

Heap Sort

$$O(n^2)$$

$$O(n)$$

$$O(\log n)$$

$$O(1)$$

Mảng đã sắp xếp

Mảng đảo ngược

Mảng ngẫu nhiên

Mảng lớn

$$O(n \log n)$$

$$O(n^2)$$

$$O(n)$$

$$O(\log n)$$

Một mảng

Hai mảng

Ba mảng

Không cần mảng

Luôn lấy phần tử ưu tiên cao nhất

Lấy ngẫu nhiên

Lấy phần tử đầu

Lấy phần tử cuối

Không ổn định, $$O(n \log n)$$

Ổn định, $$O(n^2)$$

Rất nhanh với mảng nhỏ

$$O(n)$$

Có

Không

Luôn cần mảng phụ

Không xác định

Ít hoán đổi

Rất nhanh

Ổn định

$$O(n \log n)$$

Introsort

Bubble Sort

Selection Sort

Heap Sort

Không dùng bộ nhớ phụ đáng kể

Luôn dùng mảng phụ

Chỉ dùng đệ quy

Chỉ dùng heap

Dữ liệu nhỏ, cần ít hoán đổi

Dữ liệu lớn

Cần tốc độ cao

Mảng đã sắp xếp

Selection Sort

Bubble Sort

Merge Sort

Quick Sort

1

2

5

6

N(N−1)/4

$$N^2$$

N

log N

Thứ tự ban đầu của mảng

Giá trị phần tử

Kiểu dữ liệu

Kích thước bộ nhớ

Hai phần tử đầu

Phần tử cuối

Heap

Pivot

Lấy phần tử chèn vào đoạn đã sắp xếp

Chia mảng

Phân vùng

Trộn mảng

Khoảng n/2

n

log n

1

2

1

3

4

Thỏa mãn tính chất heap

Đã sắp xếp hoàn toàn

Đảo ngược

Không thay đổi