Cụm bài Thuật toán cơ bản: 1. Big-O và sắp xếp O(n²) · 2. Đệ quy và tìm kiếm nhị phân · 3. Merge sort, quick sort
Hai đoạn code cùng đúng có thể chênh nhau từ vài mili giây tới cả tiếng với một triệu bản ghi. Đọc xong, bạn đọc được Big-O từ code, ước lượng được code có chạy kịp không, và nắm ba thuật toán sắp xếp insertion, bubble, selection. Không cần đọc gì trước; phần 2 là đệ quy, tìm kiếm nhị phân và vài bài kinh điển, phần 3 là merge sort, quick sort và cách Java thực sự sắp xếp, còn cấu trúc dữ liệu nằm ở Cấu trúc dữ liệu.
Sơ đồ tóm tắt:
flowchart TD
A["Big-O: tốc độ tăng theo n"] --> B["Nối tiếp: cộng"]
A --> C["Lồng nhau: nhân"]
A --> D["Chia đôi: O(log n)"]
E{"Chọn sort O(n²) nào?"} -->|"Mặc định"| F["Insertion: stable, gần O(n)"]
E -->|"Ghi rất đắt"| G["Selection: tối đa n-1 swap"]
E -->|"Gần như không"| H["Bubble"]
1. Độ phức tạp của thuật toán
Ý chính: độ phức tạp đo chi phí tăng thế nào khi đầu vào n lớn lên, bằng cách đếm số bước chứ không đo giây. Big-O là cách viết gọn tốc độ tăng đó.
1.1. Khái niệm
Không đo bằng giây vì kết quả phụ thuộc máy, JIT, dữ liệu. Có hai loại:
- Time complexity (độ phức tạp thời gian): số phép tính cơ bản, đếm qua số vòng lặp, số lần so sánh, số lần gán…
- Space complexity (độ phức tạp không gian): lượng bộ nhớ thuật toán cấp phát thêm.
Một bản slide ghi rõ space “không tính input và output”. Cách đếm đó gọi chính xác là auxiliary space (bộ nhớ phụ). Khi bị hỏi “space complexity”, nên hỏi lại hoặc nói rõ mình tính auxiliary space. Ví dụ merge sort cần O(n) bộ nhớ phụ, insertion sort chỉ cần O(1).
1.2. Ký hiệu Big-O
Ý chính: O(f(n)) nghĩa là với n đủ lớn, chi phí không vượt quá c · f(n) với một hằng số c nào đó. Hai quy tắc: bỏ hằng số, chỉ giữ số hạng tăng nhanh nhất.
- Bỏ hằng số:
3n + 5thànhO(n);n²/2thànhO(n²). - Giữ số hạng lớn nhất:
n² + 100n + 7thànhO(n²).
Ω, Θ, best/average/worst case và amortized
Hai ký hiệu hay bị hỏi kèm: Ω (Omega) là cận dưới, Θ (Theta) là cận chặt (vừa trên vừa dưới). Ngoài đời mọi người nói “Big-O” nhưng ý là Θ của trường hợp xấu nhất.
- Best / average / worst case: chi phí của một lần chạy với các loại đầu vào. Insertion sort tốt nhất O(n) khi mảng đã sắp xếp, xấu nhất O(n²) khi mảng ngược.
- Amortized (khấu hao): chi phí trung bình qua một chuỗi thao tác.
ArrayList.addlà O(1) amortized dù thỉnh thoảng phải resize.
1.3. Ví dụ xác định Big-O
Ý chính: mỗi phép gán là O(1); khối chạy nối tiếp thì cộng, khối lồng nhau thì nhân, rồi bỏ hằng số.
| Dạng code | Tính | Kết quả |
|---|---|---|
1. Một vòng n lần |
T(n) = c·n |
O(n) |
2. Hai vòng lồng, mỗi vòng n lần |
c·n·n |
O(n²) |
3. Vòng trong chạy i lần, i = 1..n |
c·n(n+1)/2 |
O(n²) |
| 4. Vòng trong luôn chạy 20 lần | 20·c·n |
O(n) |
5. Vòng 10 lần, nối tiếp vòng 20·n lần |
10c + 20cn |
O(n) |
| 6. Mỗi bước bỏ một nửa | n / 2^k = 1 nên k = log₂ n |
O(log n) |
O(1) gọi là hằng số: thời gian không phụ thuộc kích thước đầu vào. Công thức cần nhớ: 1 + 2 + ... + n = n(n+1)/2.
Cơ số của log không quan trọng trong Big-O vì log₂ n = log₁₀ n / log₁₀ 2, chỉ khác một hằng số.
Code của 6 ví dụ và hai cách slide minh hoạ O(log n)
Code ví dụ là của mình, minh hoạ đúng các trường hợp trong slide.
Ví dụ 1: một vòng lặp. Mỗi phép gán tốn hằng số c, tức O(1). Lặp n lần ra O(n).
int k = 0;
for (int i = 0; i < n; i++) {
k = k + 5; // O(1)
}
Ví dụ 2: hai vòng lồng nhau, mỗi vòng n lần.
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
k = k + i + j;
Ví dụ 3: vòng trong phụ thuộc vòng ngoài. Tổng c(1 + 2 + ... + n) = (c/2)n² + (c/2)n, ra O(n²).
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++)
k = k + i + j;
Ví dụ 4: vòng trong có số lần cố định. Hằng số 20 bị bỏ.
for (int i = 0; i < n; i++)
for (int j = 0; j < 20; j++)
k = k + i + j;
Ví dụ 5: hai vòng nối tiếp.
for (int j = 0; j < 10; j++) k = k + 4;
for (int i = 0; i < n; i++)
for (int j = 0; j < 20; j++)
k = k + i + j;
Ví dụ 6: O(log n). Hai bản slide dùng hai ví dụ khác nhau:
- Bản 1: tìm kiếm nhị phân. Mỗi bước loại một nửa mảng, sau
kbước cònn / 2^kphần tử; dừng khi còn 1, tứck = log₂ n. - Bản 2: tính
aⁿvớin = 2^kbằng cách bình phương liên tiếp:a² = a·a,a⁴ = a²·a², … Chỉ cầnk = log₂ nphép nhân thay vìn - 1.
// a^n với n = 2^k: bình phương k lần
static long powerOfTwoExponent(long a, int k) {
long result = a;
for (int i = 0; i < k; i++) result = result * result;
return result; // powerOfTwoExponent(3, 3) = 3^8 = 6561
}
Bài tập 1 ở phần 2 về đệ quy có cách tính xⁿ cho n bất kỳ.
1.4. So sánh các mức độ phức tạp
Ý chính: O(n log n) là ngưỡng thường chấp nhận được với n = 10⁶; O(n²) chỉ ổn tới khoảng n = 10⁴; hàm mũ và giai thừa chỉ chạy nổi với n rất nhỏ.
| Big-O | Tên | n = 10³ | n = 10⁶ | Ví dụ |
|---|---|---|---|---|
| O(1) | hằng số | 1 | 1 | truy cập a[i], HashMap.get trung bình |
| O(log n) | logarit | ~10 | ~20 | tìm kiếm nhị phân, thao tác trên TreeMap |
| O(n) | tuyến tính | 10³ | 10⁶ | duyệt mảng, tìm kiếm tuyến tính |
| O(n log n) | tuyến tính-logarit | ~10⁴ | ~2·10⁷ | merge sort, Arrays.sort |
| O(n²) | bình phương | 10⁶ | 10¹² | bubble/insertion/selection sort |
| O(n³) | bậc ba | 10⁹ (vài giây) | 10¹⁸, không khả thi | ba vòng lặp lồng nhau, nhân hai ma trận n×n kiểu ngây thơ, Floyd–Warshall |
| O(2ⁿ) | hàm mũ | không khả thi | không khả thi | Fibonacci đệ quy ngây thơ, duyệt mọi tập con |
| O(n!) | giai thừa | không khả thi | không khả thi | duyệt mọi hoán vị |
Phép thử nhân đôi. Hỏi: dữ liệu tăng gấp đôi thì chi phí tăng bao nhiêu?
| Big-O | Khi n gấp đôi, chi phí… |
Ví dụ với n từ 1 000 lên 2 000 |
|---|---|---|
| O(1) | không đổi | 1 → 1 |
| O(log n) | tăng thêm một bước | ~10 → ~11 |
| O(n) | gấp đôi | 1 000 → 2 000 |
| O(n log n) | hơi hơn gấp đôi | ~10 000 → ~22 000 |
| O(n²) | gấp bốn | 10⁶ → 4·10⁶ |
| O(2ⁿ) | bình phương (2²ⁿ = (2ⁿ)²) | không khả thi ngay từ đầu |
Dùng được cả khi đo thật: chạy với n và 2n, thời gian tăng khoảng 4 lần thì gần như chắc có một vòng lặp lồng O(n²) đâu đó.
Ghi chú về biểu đồ slide và nhóm O(n³), O(2ⁿ), O(n!)
- Biểu đồ trong slide có thêm đường O(n³), ghi nhầm là “O(x³)”, “O(x²)” (dùng
xthay chon). - Ở
n = 10³, O(n³) còn chạy được trong vài giây, nhưngnlên 10⁴ là thành 10¹², vài tiếng. - O(2ⁿ) thường gặp ở thuật toán quay lui (backtracking) không cắt nhánh; O(n!) ở bài sinh mọi hoán vị. Cả hai chỉ chạy nổi với
nrất nhỏ: cỡ 20–25 cho 2ⁿ, cỡ 10–12 cho n!.
2. Các thuật toán sắp xếp cơ bản
Ý chính: ba thuật toán đều O(n²), khác nhau ở trường hợp tốt nhất, tính stable và số lần swap. Học chúng để có chiến lược giải bài và hiểu sort của thư viện, không phải để dùng thay Arrays.sort.
Hai khái niệm cần biết trước:
- Stable (ổn định): hai phần tử có khoá bằng nhau giữ nguyên thứ tự tương đối như ban đầu.
- In-place (tại chỗ): chỉ cần O(1) bộ nhớ phụ.
Vì sao phải học sắp xếp khi đã có Arrays.sort
Slide đưa ra ba lý do và mình đồng ý:
- Các thuật toán sắp xếp thể hiện nhiều chiến lược giải bài (tăng dần, chia để trị, chọn phần tử tốt nhất…) áp dụng được cho bài khác.
- Bài tập tốt để luyện kỹ năng lập trình cơ bản: vòng lặp, điều kiện, mảng, method.
- Ví dụ rõ nhất để so sánh hiệu năng giữa các thuật toán.
Lý do thứ tư cho người làm backend: hiểu stable và in-place giúp biết khi nào sort của thư viện cho kết quả đúng ý (xem phần 3).
2.1. Insertion sort (sắp xếp chèn)
Ý chính: giữ đoạn đầu mảng luôn đã sắp xếp; mỗi bước lấy phần tử kế tiếp và chèn vào đúng chỗ trong đoạn đó, giống xếp bài khi bốc từng lá.
static void insertionSort(int[] a) {
for (int i = 1; i < a.length; i++) {
int current = a[i];
int k = i - 1;
while (k >= 0 && a[k] > current) { // dùng > (không phải >=) để giữ stable
a[k + 1] = a[k];
k--;
}
a[k + 1] = current;
}
}
- Độ phức tạp: xấu nhất / trung bình O(n²), tốt nhất O(n) khi mảng gần như đã sắp xếp (vòng
whilegần như không chạy). - Stable, in-place, online (sắp xếp được khi dữ liệu đến từng phần tử).
- Rất nhanh với mảng nhỏ vì ít overhead. Vì vậy thuật toán sắp xếp của JDK chuyển sang insertion sort cho các đoạn ngắn vài chục phần tử.
Các bước insertion sort và ví dụ chạy tay [5, 2, 4, 1]
- Với
itừ 1 đếnn-1, đặtcurrent = a[i]. Lúc nàya[0..i-1]đã sắp xếp. - Đi lùi
ktừi-1về 0: nếua[k] > currentthì dờia[k]sang phải một ô (a[k+1] = a[k]). - Gặp
a[k] <= current(hoặc hết mảng) thì dừng và đặta[k+1] = current.
| i | current | Mảng sau bước |
|---|---|---|
| 1 | 2 | [2, 5, 4, 1] |
| 2 | 4 | [2, 4, 5, 1] |
| 3 | 1 | [1, 2, 4, 5] |
2.2. Bubble sort (sắp xếp nổi bọt)
Ý chính: so từng cặp kề nhau và đổi chỗ nếu bên trái lớn hơn; sau mỗi lượt, phần tử lớn nhất còn lại “nổi” về cuối đoạn chưa sắp xếp.
Sửa cách slide đánh chỉ số cho bubble sort
Slide mô tả chỉ số hơi lẫn (“tại lần lặp k = 0..n, tìm được phần tử lớn thứ n và đẩy xuống vị trí n - i”). Chính xác là: sau lượt thứ k (đếm từ 0), phần tử lớn thứ k+1 đã nằm đúng ở vị trí n-1-k, nên lượt sau chỉ cần đi tới n-2-k.
static void bubbleSort(int[] a) {
for (int end = a.length - 1; end > 0; end--) {
boolean swapped = false;
for (int j = 0; j < end; j++) {
if (a[j] > a[j + 1]) {
int tmp = a[j]; a[j] = a[j + 1]; a[j + 1] = tmp;
swapped = true;
}
}
if (!swapped) return; // một lượt không đổi chỗ nào -> đã sắp xếp
}
}
- Độ phức tạp: O(n²); nhờ cờ
swapped, tốt nhất O(n). - Stable, in-place.
- Gần như không dùng trong thực tế: số lần swap nhiều nhất trong ba thuật toán.
2.3. Selection sort (sắp xếp chọn)
Ý chính: tìm phần tử nhỏ nhất đưa về vị trí đầu, tìm nhỏ nhất trong phần còn lại đưa về vị trí thứ hai, cứ thế tiếp tục.
static void selectionSort(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
int min = i;
for (int j = i + 1; j < a.length; j++)
if (a[j] < a[min]) min = j;
if (min != i) {
int tmp = a[i]; a[i] = a[min]; a[min] = tmp;
}
}
}
- Độ phức tạp: luôn O(n²) phép so sánh, kể cả khi mảng đã sắp xếp.
- In-place nhưng không stable: phép swap đường dài có thể nhảy một phần tử qua phần tử bằng nó. Ví dụ
[2a, 2b, 1]: swap2avới1cho[1, 2b, 2a]. - Điểm mạnh duy nhất: tối đa n - 1 lần swap, có ích khi thao tác ghi rất đắt.
2.4. So sánh ba thuật toán
Ý chính: cần chọn thì chọn insertion sort; selection sort chỉ khi ghi rất đắt; bubble sort gần như không bao giờ.
Xem minh hoạ trực quan
Ý chính: chạy animation từng bước với vài mảng tự chọn là cách nhanh nhất để nhớ ba thuật toán.
Animation từ sách của Y. Daniel Liang:
- Insertion sort: https://liveexample.pearsoncmg.com/dsanimation/InsertionSortNeweBook.html
- Bubble sort: https://liveexample.pearsoncmg.com/dsanimation/BubbleSortNeweBook.html
- Selection sort: http://liveexample.pearsoncmg.com/dsanimation/SelectionSortNeweBook.html
Bài tập
Bài 1: In mảng theo thứ tự lớn nhất, nhỏ nhất, lớn nhì, nhỏ nhì…
Đề (diễn đạt lại): cho mảng n số nguyên phân biệt (1 ≤ n ≤ 1000), in ra theo thứ tự: lớn nhất, nhỏ nhất, lớn thứ hai, nhỏ thứ hai, … Ví dụ {9, 7, 12, 8, 6, 5} cho ra 12 5 9 6 8 7.
Lời giải Bài 1: sắp xếp rồi hai con trỏ
Sắp xếp tăng dần, rồi dùng hai con trỏ: hi đi từ cuối, lo đi từ đầu, lấy xen kẽ.
static int[] maxMinOrder(int[] input) {
int[] a = input.clone(); // không sửa mảng của người gọi
Arrays.sort(a);
int[] out = new int[a.length];
int lo = 0, hi = a.length - 1, k = 0;
while (lo <= hi) {
out[k++] = a[hi--];
if (lo <= hi) out[k++] = a[lo++]; // n lẻ: phần tử giữa chỉ được lấy một lần
}
return out;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) a[i] = in.nextInt();
StringJoiner sj = new StringJoiner(" ");
for (int v : maxMinOrder(a)) sj.add(String.valueOf(v));
System.out.println(sj);
}
O(n log n) do bước sort, hai con trỏ chỉ O(n). Với n ≤ 1000 thì tự viết insertion sort cũng chạy kịp (khoảng 10⁶ phép), một chỗ hợp lý để dùng lại mục 2.
Ghi nhớ
- Đọc được Big-O của một đoạn code có vòng lồng, vòng nối tiếp và vòng chia đôi.
- Nói được thời gian thay đổi thế nào khi
ngấp đôi, và dùng 10⁸ phép/giây để ước lượng. - Phân biệt được worst case, average case và amortized (ví dụ
ArrayList.add). - Giải thích được vì sao selection sort không stable và vì sao insertion sort vẫn có trong JDK.
- Chỉ ra được lỗi
a[i]thay vìa[min]bằng phản ví dụ[3, 1, 2].
Câu hỏi phỏng vấn
Junior
Big-O là gì? Vì sao bỏ hằng số?
Big-O là cận trên của tốc độ tăng chi phí khi n lớn dần; hằng số bị bỏ vì với n đủ lớn, dạng của hàm mới quyết định.
Hằng số phụ thuộc máy, ngôn ngữ, compiler; còn n so với n² là khác biệt về bản chất. Dù vậy, với n nhỏ thì hằng số vẫn có ý nghĩa trong thực tế.
Stable sort nghĩa là gì?
Các phần tử có khoá bằng nhau giữ nguyên thứ tự tương đối như trước khi sắp xếp.
Insertion và bubble sort là stable; selection sort thì không.
Nếu dữ liệu tăng gấp đôi, thời gian chạy của O(1), O(log n), O(n), O(n²) thay đổi thế nào?
O(1) không đổi, O(log n) thêm một bước, O(n) gấp đôi, O(n²) gấp bốn.
O(log n) chỉ thêm một bước vì log₂(2n) = log₂ n + 1. O(n log n) hơn gấp đôi một chút; O(2ⁿ) bị bình phương. Đây cũng là cách kiểm tra nhanh bằng benchmark: đo với n và 2n, tỉ lệ thời gian cho biết bậc tăng.
Mid
Một bản selection sort viết if (a[j] < a[i]) min = j;. Sai ở đâu, cho phản ví dụ?
Phải so với a[min] (giá trị nhỏ nhất tìm được đến giờ), không phải a[i]; phản ví dụ [3, 1, 2] cho ra [2, 1, 3].
So với a[i] thì min chỉ là vị trí cuối cùng nhỏ hơn a[i]. Với [3, 1, 2], lượt đầu min = 2, swap ra [2, 1, 3], các lượt sau không đổi gì. Bài học: với thuật toán “chọn phần tử tốt nhất”, biến tốt nhất phải là thứ được so sánh; và luôn test bằng mảng nhỏ có nhiều phần tử cạnh tranh, đối chiếu với Arrays.sort.
Vì sao insertion sort vẫn được dùng trong thư viện chuẩn dù là O(n²)?
Vì với mảng nhỏ hằng số của nó rất thấp, và với dữ liệu gần sắp xếp nó gần O(n).
Không gọi đệ quy, truy cập tuần tự, ít overhead. Vì vậy các thuật toán hỗn hợp như TimSort và dual-pivot quicksort của JDK chuyển sang insertion sort cho các đoạn nhỏ (vài chục phần tử).
Best case, average case, worst case và amortized khác nhau thế nào?
Best/average/worst case nói về một lần chạy với các loại đầu vào; amortized là trung bình trên một chuỗi thao tác, không cần giả định xác suất.
- Insertion sort: tốt nhất O(n) khi mảng đã sắp xếp, xấu nhất O(n²) khi mảng ngược, trung bình O(n²).
ArrayList.addcó lần O(n) khi resize, nhưng n lầnaddtốn tổng O(n), nên mỗi lần là O(1) amortized.- Average case cần giả định phân phối dữ liệu, amortized thì không.
Vì sao selection sort không stable? Khi nào nó vẫn đáng dùng?
Vì phép swap “đường dài” có thể đưa một phần tử nhảy qua phần tử khác cùng khoá; nó chỉ đáng dùng khi ghi rất đắt.
Ví dụ [2a, 2b, 1]: swap 2a với 1 cho [1, 2b, 2a], thứ tự hai số 2 bị đảo. Điểm mạnh duy nhất là chỉ swap tối đa n - 1 lần, có ích khi ghi đắt (ví dụ ghi vào flash memory); còn lại insertion sort tốt hơn.
Senior
Khi nào O(n log n) lại chậm hơn O(n²) trong thực tế?
Khi n nhỏ: hằng số và yếu tố phần cứng chiếm ưu thế, vì Big-O chỉ nói về xu hướng khi n → ∞.
Insertion sort trên 20 phần tử nhanh hơn merge sort vì không cấp phát, không đệ quy, truy cập tuần tự. Đó là lý do có các thuật toán lai, và lý do phải đo bằng benchmark (JMH) thay vì chỉ suy luận.
Từ vựng tiếng Anh
| Term | Phát âm | Nghĩa | Ví dụ câu trong phỏng vấn |
|---|---|---|---|
| time complexity | /taɪm kəmˈplɛksəti/ | độ phức tạp thời gian | “The time complexity is O(n log n) because of the sort.” |
| auxiliary space | /ɔːɡˈzɪliəri speɪs/ | bộ nhớ phụ | “It runs in O(1) auxiliary space, ignoring the input.” |
| upper bound | /ˈʌpər baʊnd/ | cận trên | “Big-O gives an upper bound on the growth rate.” |
| worst case / best case | /wɜːrst keɪs/ | trường hợp xấu nhất / tốt nhất | “In the worst case, insertion sort is quadratic.” |
| quadratic | /kwɑːˈdrætɪk/ | bình phương | “Two nested loops over the input give quadratic time.” |
| logarithmic | /ˌlɔːɡəˈrɪðmɪk/ | logarit | “Binary search is logarithmic because it halves the range each step.” |
| stable sort | /ˈsteɪbəl sɔːrt/ | sắp xếp ổn định | “A stable sort keeps equal elements in their original order.” |
| in-place | /ɪn pleɪs/ | tại chỗ | “Selection sort is in-place but not stable.” |
- “If the input doubles, a quadratic algorithm takes four times as long, so this won’t scale.”
- “Insertion sort is my pick among the three: it’s stable, in-place, and nearly linear on almost-sorted data.”
- “Amortized cost is averaged over a sequence of operations, not over random inputs.”
- “Selection sort isn’t stable because the long-distance swap can jump an element over an equal one.”
Ghi chép dựa trên khoá Fundamentals of Backend (Ronin Engineer) và tài liệu Java Core của Hỏi Dân IT, viết lại theo cách hiểu của mình.