https://www.facebook.com/676558635548484/

Tay Ninh Algorithm Group, Phường Tân Ninh, Tây Ninh (2026)

25/11/2025

[Thuật toán - 9] PREFIX SUM (TỔNG TÍCH LŨY)

1. Khái niệm

Prefix sum là kỹ thuật tiền xử lý một mảng để trả lời nhanh các truy vấn dạng tổng đoạn.
Ta xây dựng mảng prefix[] sao cho:

prefix[i] = a[1] + a[2] + ... + a[i]

Khi đó tổng đoạn [l, r] được tính trong O(1):

sum(l, r) = prefix[r] - prefix[l-1]

---

2. Tính chất

Xây prefix: O(n)

Query tổng đoạn: O(1)

Không thay đổi dữ liệu gốc (nếu cần cập nhật giá trị thì phải dùng Fenwick Tree/Segment Tree).

---

3. Cách tạo prefix sum

3.1. Một chiều

vector a(n+1), prefix(n+1);
for (int i = 1; i > q;
vector a(n+1), pref(n+1);

for(int i = 1; i > a[i];
pref[i] = pref[i-1] + a[i];
}

while(q--) {
int l, r;
cin >> l >> r;
cout

25/11/2025

[Thuật toán – 8] Two Pointers

1. Ý tưởng chính

Two Pointers sử dụng hai con trỏ (thường là l và r) chạy trên một mảng hoặc chuỗi để xử lý bài toán trong O(n) thay vì O(n²).

Mỗi con trỏ chỉ tăng (hoặc giảm) một chiều, không bao giờ lùi lại → tổng số bước là tuyến tính.

---

2. Điều kiện thường gặp

Two Pointers đặc biệt hiệu quả khi:

Dữ liệu đã sắp xếp.

Dãy không âm, hoặc đáp án đơn điệu theo dịch chuyển con trỏ.

Cần duy trì một cửa sổ (sliding window) của mảng.

---

3. Hai dạng phổ biến

3.1. Two pointers trên mảng đã sắp xếp

Dùng khi cần tìm:

cặp có tổng = k

cặp gần nhất

đếm số cặp thỏa điều kiện

Cách làm:

1. l = 0, r = n-1.

2. Tùy điều kiện, tăng l hoặc giảm r.

Thời gian luôn O(n).

---

3.2. Sliding Window

Một phiên bản đặc biệt, thường với dãy không âm:

Mở rộng r để tăng tổng.

Thắt l để giảm tổng.

Dùng để tìm:

subarray có tổng ≤ k

subarray dài nhất/thỏa điều kiện

đếm số subarray hợp lệ

Thời gian O(n) vì mỗi chỉ số được đi qua tối đa 1 lần.

---

4. Pseudocode – Tìm tổng bằng k (mảng tăng)

---

l = 0 r = n - 1

while l < r: s = A[l] + A[r] if s == k: return (l, r) if s < k: l += 1 else: r -= 1

return "not found"

---

5. Pseudocode – Sliding Window (subarray có tổng ≤ k)

---

l = 0 sum = 0 ans = 0

for r in range(n): sum += A[r] while sum > k: sum -= A[l] l += 1 ans = max(ans, r - l + 1)

---

6. Ví dụ minh họa

A = [1, 3, 4, 5, 7, 10], k = 9

l=0, r=5 → 1+10=11 > 9 → giảm r

l=0, r=4 → 1+7=8 < 9 → tăng l

l=1, r=4 → 3+7=10 > 9 → giảm r

l=1, r=3 → 3+5=8 < 9 → tăng l

l=2, r=3 → 4+5=9 → tìm thấy

---

7. Độ phức tạp

Thời gian: O(n)

Không gian: O(1)

Hiệu quả hơn O(n²) rất nhiều trong bài toán cặp đôi hoặc subarray.

---

8. Ứng dụng

Tìm 2 số có tổng = k (2-sum dạng sorted).

Đếm số cặp thỏa điều kiện A[r] − A[l] ≤ k.

Tìm subarray dài nhất thỏa tổng ≤ k.

Tìm subarray chứa không quá K số khác nhau.

Xử lý chuỗi: cửa sổ chứa tối đa K ký tự khác nhau.

Tối ưu độ dài đoạn, khoảng cách, subarray.

---

9. Lỗi hay gặp

Quên điều kiện mảng phải sắp xếp (với dạng hai đầu).

Không đảm bảo dữ liệu không âm khi dùng sliding window tổng.

Cập nhật sai khi tăng/giảm con trỏ.

Tính toán cửa sổ sai (off-by-one).

---

10. Trong lập trình thi đấu

Two Pointers là một trong những kỹ thuật bắt buộc phải thành thạo, ngang hàng với:

binary search

prefix sum

sorting

greedy cơ bản

Bài về subarray, đoạn liên tiếp, hoặc cặp giá trị đều có khả năng giải O(n) bằng two pointers.

25/11/2025

[Thuật toán – 7] Binary Search

1. Ý tưởng chính

Binary Search tìm kiếm trên mảng đã sắp xếp bằng cách chia đôi khoảng tìm kiếm:

1. Lấy vị trí giữa mid.

2. So sánh A[mid] với giá trị cần tìm x.

3. Nếu A[mid] == x → tìm thấy.

4. Nếu A[mid] < x → tìm ở nửa phải.

5. Nếu A[mid] > x → tìm ở nửa trái.

Mỗi bước loại bỏ một nửa không cần thiết → thời gian rất nhỏ, log₂(n).

---

2. Điều kiện bắt buộc

Dữ liệu phải được sắp xếp tăng (hoặc giảm, nhưng phải đồng nhất).

Không dùng cho mảng chưa sort.

Phù hợp cho tìm kiếm nhanh, nhiều truy vấn.

---

3. Cách xây dựng thuật toán

Có hai dạng:

Binary search thường: tìm vị trí x.

Lower_bound / upper_bound: tìm vị trí chèn.

Binary search trên đáp án: tìm nghiệm trong không gian đáp án (CP dùng rất nhiều).

---

4. Pseudocode – Tìm x trong mảng tăng

---

binarySearch(A, x): l = 0 r = len(A) - 1

while l 8 → tìm bên trái

mid = 3 → A[3] = 8 → trả về 3

---

6. Độ phức tạp

Thời gian: Θ(log n)

Không gian: O(1)

Rất hiệu quả khi n lớn (10⁶ → chỉ ~20 lần so sánh).

---

7. Ứng dụng

Tìm kiếm trong mảng đã sắp: index, tồn tại hay không.

Tìm lower_bound/upper_bound (cực kỳ phổ biến trong CP).

Tìm vị trí phù hợp để insert/replace.

Tìm đáp án trong các bài toán tối ưu (binary search on answer):

tìm max/min thỏa điều kiện

tìm smallest x sao cho f(x) = true

tìm ngưỡng trong các hàm đơn điệu

---

8. Biến thể quan trọng trong thi đấu

8.1. Lower Bound – tìm phần tử >= x đầu tiên

---

lower_bound(A, x): l = 0; r = len(A) while l < r: mid = (l + r) // 2 if A[mid] >= x: r = mid else: l = mid + 1 return l

8.2. Upper Bound – tìm phần tử > x đầu tiên

---

upper_bound(A, x): l = 0; r = len(A) while l < r: mid = (l + r) // 2 if A[mid] > x: r = mid else: l = mid + 1 return l

---

9. Lỗi hay gặp

Vòng l

25/11/2025

[Thuật toán – 6] Heap Sort

1. Ý tưởng chính

Heap Sort xây dựng max-heap (đống tối đa) từ mảng, sau đó lặp lại quy trình:

1. Hoán đổi phần tử lớn nhất (root) với phần tử cuối.

2. Giảm kích thước heap.

3. Heapify để khôi phục tính chất max-heap.

Cuối cùng thu được mảng tăng dần.

---

2. Cấu trúc nền tảng

Max-heap: cây nhị phân hoàn chỉnh, mỗi node ≥ con của nó.
Chỉ cần lưu bằng array (không cần struct tree riêng).

Index con và cha:

left(i) = 2i + 1

right(i) = 2i + 2

parent(i) = (i – 1) / 2

---

3. Cách xây dựng thuật toán

Bước 1 – Build Heap

Từ mảng A ban đầu, chạy heapify từ node cuối có con:
i = n/2 – 1 → 0

Bước 2 – Sort

Lặp từ i = n−1 → 1:

swap(A[0], A[i])

heapify(A, 0, heapSize = i)

---

4. Pseudocode

---

heapSort(A): n = len(A)

for i = n/2 - 1 downto 0:
heapify(A, n, i)

for i = n-1 downto 1:
swap(A[0], A[i])
heapify(A, i, 0)

---

Heapify:

---

heapify(A, heapSize, i): largest = i l = 2i + 1 r = 2i + 2

if l < heapSize and A[l] > A[largest]:
largest = l
if r < heapSize and A[r] > A[largest]:
largest = r

if largest != i:
swap(A[i], A[largest])
heapify(A, heapSize, largest)

---

---

5. Ví dụ ngắn

A = [4, 10, 3, 5, 1]

Build max-heap → [10, 5, 3, 4, 1]

Swap 10 với 1 → [1, 5, 3, 4, 10]

Heapify → [5, 4, 3, 1, 10]

Swap 5 với 1 → …

…

Kết quả: [1, 3, 4, 5, 10]

---

6. Độ phức tạp

Build heap: O(n)

Quá trình sort: n lần heapify → n × O(log n)

Tổng: Θ(n log n)

Không gian phụ: O(1)
Không ổn định.

---

7. Ưu điểm

Không dùng bộ nhớ phụ (in-place).

Không bị worst-case tệ như quicksort O(n²).

Tính toán chi tiết rõ ràng, phù hợp bài dạng cấu trúc dữ liệu.

---

8. Nhược điểm

Không ổn định.

Overhead heapify nhiều → thường chậm hơn std::sort.

Cache efficiency kém hơn các thuật toán dựa trên chia tách (divide-and-conquer).

---

9. Khi nào dùng / không dùng

Dùng khi:

Cần in-place, không thể cấp thêm O(n).

Cần worst-case O(n log n).

Đề yêu cầu sử dụng heap.

Không dùng khi:

Cần hiệu năng cao nhất (std::sort nhanh hơn).

Cần tính ổn định.

Dữ liệu nhỏ (insertion sort phù hợp hơn).

---

10. Ứng dụng

Triển khai priority queue.

Dùng khi giới hạn RAM sát nút.

Đề thi yêu cầu tự viết heapsort hoặc heapify.

25/11/2025

[Thuật toán – 5] Radix Sort

1. Ý tưởng chính

Radix Sort sắp xếp từng chữ số (digit) của số nguyên, từ chữ số thấp nhất (L*D) hoặc cao nhất (HSD). Mỗi lần xử lý một chữ số, thuật toán sử dụng một bộ sắp xếp ổn định, thường là Counting Sort.

Tư duy: thay vì so sánh toàn bộ số, gom nhóm theo từng chữ số.

---

2. Phương pháp L*D (Least Significant Digit)

Phổ biến trong lập trình thi đấu.

Xử lý lần lượt chữ số hàng đơn vị → hàng chục → hàng trăm → ... → đến chữ số lớn nhất.

Chữ số sau khi sắp xếp phải ổn định, vì thứ tự từ các digit trước phải được giữ.

---

3. Cách xây dựng thuật toán

Giả sử sắp xếp số nguyên không âm.

1. Xác định số chữ số lớn nhất (maxDigit).

2. Với mỗi digit d từ 0 → maxDigit-1:

Thực hiện Counting Sort theo digit thứ d.

Counting Sort lúc này chạy trên phạm vi [0..9].

---

4. Pseudocode

---

radixSort(A): maxVal = max(A) exp = 1 while maxVal // exp > 0: countingSortDigit(A, exp) exp *= 10

Counting Sort theo digit:

---

countingSortDigit(A, exp): C[0..9] = {0} B = array same size as A

for x in A:
digit = (x // exp) % 10
C[digit] += 1

for i = 1..9:
C[i] += C[i-1]

for i = len(A)-1 downto 0:
digit = (A[i] // exp) % 10
B[C[digit] - 1] = A[i]
C[digit] -= 1

copy B to A

---

---

5. Ví dụ

A = [170, 45, 75, 90, 802, 24, 2, 66]

Lần 1 (exp=1, hàng đơn vị):
→ [170, 90, 802, 2, 24, 45, 75, 66]

Lần 2 (exp=10, hàng chục):
→ [802, 2, 24, 45, 66, 170, 75, 90]

Lần 3 (exp=100, hàng trăm):
→ [2, 24, 45, 66, 75, 90, 170, 802]

---

6. Độ phức tạp

Thời gian: Θ((n + k) * d)

d = số chữ số

k = 10 (digit), nên trong thực tế: Θ(n * d)

Không gian phụ: O(n + k)

Sắp xếp ổn định.

Khi d nhỏ và giá trị không quá lớn, Radix Sort có thể nhanh hơn comparison sort.

---

7. Ưu điểm

Thời gian gần như tuyến tính nếu d nhỏ.

Không so sánh trực tiếp số → không gặp worst-case kiểu quicksort.

Ổn định.

---

8. Nhược điểm

Phụ thuộc vào số chữ số.

Cần Counting Sort ổn định.

Không thích hợp cho số quá lớn (nhiều chữ số).

Không hợp với object phức tạp hoặc số thực.

---

9. Khi nào dùng / không dùng

Dùng khi:

Cần tốc độ tuyến tính cho số nguyên 32-bit hoặc 64-bit.

Bài có giới hạn giá trị nhỏ hoặc d cố định.

Tần suất sử dụng Counting Sort thuận lợi.

Không dùng khi:

Dữ liệu không phải số nguyên.

Giá trị rất lớn (nhiều digit).

Ram hạn chế.

---

10. Ứng dụng

Sắp xếp log, record có khóa số nguyên cố định

Hệ thống indexing, số ID cố định độ dài

Chuẩn bị cho xử lý chuỗi dạng số (kết hợp Count Sort)

25/11/2025

[Thuật toán – 4] Counting Sort

1. Ý tưởng chính

Counting Sort không so sánh các phần tử. Thuật toán đếm số lần xuất hiện của từng giá trị, sau đó tính vị trí cuối cùng của mỗi giá trị trong mảng đã sắp xếp.

Điều kiện: giá trị đầu vào phải nằm trong khoảng hữu hạn và không quá lớn.

---

2. Cách xây dựng thuật toán

Giả sử mảng A có n phần tử, và giá trị nằm trong [0..k].

Bước thực hiện:

1. Tạo mảng đếm C[0..k], khởi tạo 0.

2. Duyệt A, tăng C[a[i]].

3. Chuyển C thành prefix sum để xác định vị trí cuối cùng của mỗi giá trị.

4. Duyệt ngược A, đặt từng phần tử vào mảng kết quả B theo C[a[i]] rồi giảm C[a[i]].

---

3. Pseudocode

---

countingSort(A, k): C = array[0..k] = {0} for x in A: C[x] += 1

for i = 1..k:
C[i] += C[i-1]

B = array same size as A

for i = len(A)-1 downto 0:
v = A[i]
B[C[v] - 1] = v
C[v] -= 1

return B

---

---

4. Ví dụ

A = [4, 2, 2, 8, 3, 3, 1]

Đếm:
C = [0,1,0,2,1,0,0,0,1] (theo giá trị 1..8)

Prefix sum:
C = [1,1,3,4,4,4,4,5]

Duyệt ngược và đặt vào kết quả →
[1,2,2,3,3,4,8]

---

5. Độ phức tạp

Thời gian: Θ(n + k)

Không gian phụ: O(n + k)

Ổn định nếu thực hiện theo hướng duyệt ngược.

---

6. Ưu điểm

Không so sánh → rất nhanh khi k nhỏ.

Ổn định.

Dùng làm nền cho Radix Sort (sắp xếp số lớn theo từng chữ số).

---

7. Nhược điểm

Cần bộ nhớ O(k).

Không thích hợp khi giá trị quá lớn so với n.

Không dùng được khi dữ liệu không phải số nguyên có phạm vi rõ ràng.

---

8. Khi nào dùng / không dùng

Dùng khi:

Giá trị nằm trong khoảng nhỏ, ví dụ [0..10⁵] và n rất lớn.

Cần sắp xếp tuyến tính.

Dữ liệu dạng tần suất cao, phân bố giá trị thấp.

Không dùng khi:

Giá trị lớn hoặc không biết trước.

Bộ nhớ hạn chế.

Khi mảng là số thực, string dài, object phức tạp (vì không đếm trực tiếp được).

---

9. Ứng dụng

Là bước con trong Radix Sort.

Sắp xếp phân loại theo khóa nhỏ: điểm số, màu, số lượng nhóm cố định.

Dùng trong các bài toán tính tần suất, thống kê nhanh.

25/11/2025

[Thuật toán – 3] std::sort trong C++

1. std::sort là gì?

std::sort là hàm sắp xếp mặc định trong thư viện của C++. Đây là thuật toán sắp xếp không ổn định, tối ưu cho hiệu năng khi chạy trong bộ nhớ (in-memory sorting).

---

2. Ý tưởng chính – Introsort

std::sort dùng Introspective Sort (Introsort):

Bắt đầu bằng quicksort (nhanh trên thực tế).

Nếu độ sâu đệ quy vượt ngưỡng → chuyển sang heapsort để đảm bảo O(n log n) worst-case.

Khi đoạn dữ liệu nhỏ → dùng insertion sort để giảm overhead.

Cách phối hợp 3 thuật toán này giúp std::sort nhanh, ổn định về hiệu năng và an toàn trong trường hợp dữ liệu gây worst-case.

---

3. Độ phức tạp

Thời gian – Worst/Average/Best:
Θ(n log n)

Không gian phụ trợ:
O(log n) do ngăn xếp đệ quy.

Tính chất:

Không ổn định.

In-place (không cần O(n) mảng phụ).

Rất nhanh trong thực tế.

---

4. Ưu điểm

Hiệu năng xuất sắc cho dữ liệu nằm trong RAM.

Không cần nhiều bộ nhớ bổ sung.

Phù hợp xử lý real-time, hệ thống cần tốc độ cao.

Được tối ưu hoá trong các compiler hiện đại.

---

5. Nhược điểm

Không ổn định (thứ tự record bằng nhau có thể bị đảo).

Không phù hợp cho sorting ngoại vi (external sort) vì không phải merge-based.

Không đảm bảo tính dự đoán về vị trí final của các phần tử bằng nhau.

---

6. Khi nào dùng / không dùng

Dùng std::sort khi:

Cần tốc độ tối đa cho mảng/ vector trong RAM.

Không quan trọng tính ổn định.

Dữ liệu kích thước nhỏ đến rất lớn nhưng vẫn nằm trong bộ nhớ.

Không nên dùng khi:

Cần sắp xếp ổn định → dùng std::stable_sort.

Không muốn worst-case phải phụ thuộc vào heapsort.

Dữ liệu quá lớn vượt RAM → dùng merge sort dạng external.

---

7. Code mẫu

-------------------
int main() {
vector a = {5, 2, 3, 1, 4};
sort(a.begin(), a.end());
}

Có thể truyền comparator:

sort(a.begin(), a.end(), [](int x, int y){
return x > y; // sort giảm dần
});
-------------------

8. Ứng dụng thực tế

Hệ thống yêu cầu tốc độ cao: game engine, real-time system.

Sắp xếp dữ liệu lớn nhưng nằm trong RAM: mảng số, record nhẹ, object nhỏ.

Là thuật toán mặc định trong nhiều thư viện C++ ứng dụng performance-critical.

27/09/2025

[Thuật toán - 2] Merge Sort

1. Ý tưởng chính

Chia mảng thành 2 nửa → sắp xếp đệ quy từng nửa → gộp (merge) 2 nửa đã sắp thành một mảng hoàn chỉnh.
Cốt lõi: merge step – trộn 2 mảng con đã sắp xếp thành một mảng lớn, giữ đúng thứ tự.

2. Cách xây dựng thuật toán

Pseudocode:
----------------------------------------------------------------
mergeSort(A, l, r):
if l < r:
m = (l + r) // 2
mergeSort(A, l, m)
mergeSort(A, m+1, r)
merge(A, l, m, r) // trộn 2 mảng con A[l..m], A[m+1..r]
----------------------------------------------------------------
Hàm merge dùng 2 con trỏ chạy qua 2 mảng con, so sánh từng cặp, đưa phần tử nhỏ hơn vào mảng tạm, cuối cùng copy lại.

Ví dụ:

- Mảng: [5, 2, 4, 6, 1, 3]

- Chia thành [5,2,4] và [6,1,3]

- [5,2,4] → chia tiếp [5,2] và [4] → [5,2] thành [5] + [2] → merge → [2,5] → merge [2,5] với [4] → [2,4,5]

- [6,1,3] → chia [6,1] + [3] → [6,1] thành [6] + [1] → merge → [1,6] → merge [1,6] với [3] → [1,3,6]

- Merge cuối: [2,4,5] và [1,3,6] → [1,2,3,4,5,6].

3. Code mẫu

- C++:
----------------------------------------------------------------
void merge(vector& a, int l, int m, int r) {
vector left(a.begin()+l, a.begin()+m+1);
vector right(a.begin()+m+1, a.begin()+r+1);
int i=0, j=0, k=l;
while (i < left.size() && j < right.size()) {
if (left[i]

27/09/2025

[Thuật toán - 1] Sắp xếp chèn (Insertion sort)

1. Ý tưởng chính

Giữ một prefix (phần đầu mảng) luôn đã được sắp xếp. Lần lượt lấy từng phần tử phía sau (gọi là key) và chèn nó vào đúng vị trí trong prefix đã sắp xếp bằng cách dịch các phần tử lớn hơn sang phải. Nghĩ đơn giản: sắp từng cái một như khi xếp bài trên tay.

2. Cách xây dựng thuật toán

Pseudocode cơ bản (mảng a[0..n-1]):
----------------------------------------------------------------
for i = 1 to n-1:
key = a[i]
j = i - 1
while j >= 0 and a[j] > key:
a[j+1] = a[j] // dịch sang phải
j = j - 1
a[j+1] = key // chèn key vào chỗ trống
----------------------------------------------------------------
while a[j] > key (chứ không phải >=) đảm bảo tính ổn định (equal giữ thứ tự cũ).

Ví dụ từng bước

- Mảng: [5, 2, 4, 6, 1, 3]

- i=1, key=2 → dịch 5 → [2,5,4,6,1,3]

- i=2, key=4 → chèn giữa 2 và 5 → [2,4,5,6,1,3]

- i=3, key=6 → đã đúng chỗ → [2,4,5,6,1,3]

- i=4, key=1 → dịch 6,5,4,2 → [1,2,4,5,6,3]

- i=5, key=3 → dịch 6,5,4 → [1,2,3,4,5,6]

Code mẫu

- C++ (in-place, ổn định):
----------------------------------------------------------------
void insertionSort(vector& a) {
int n = a.size();
for (int i = 1; i < n; ++i) {
int key = a[i];
int j = i - 1;
while (j >= 0 && a[j] > key) {
a[j+1] = a[j];
--j;
}
a[j+1] = key;
}
}
----------------------------------------------------------------
- Python:
----------------------------------------------------------------
def insertion_sort(a):
for i in range(1, len(a)):
key = a[i]
j = i - 1
while j >= 0 and a[j] > key:
a[j+1] = a[j]
j -= 1
a[j+1] = key
----------------------------------------------------------------
3. Độ phức tạp thời gian

Best case (mảng đã sắp xếp tăng): O(n) — mỗi phần tử chỉ so sánh 1 lần, không dịch.

Average case (mảng ngẫu nhiên): Θ(n²). Trung bình khoảng ~ n^2 / 4 so sánh/ dịch (hệ số không quan trọng khi nói O-notation).

Worst case (mảng giảm dần): Θ(n²). Tổng số phép so sánh/dịch ≈ n(n−1)/2.

Giải thích ngắn: phần tử i có thể dịch lên đến i vị trí → tổng chạy là sum(i) = n(n−1)/2.

4. Độ phức tạp không gian

O(1) phụ trợ (in-place). Chỉ cần biến tạm key.

5. Tính chất

Ổn định (stable) nếu dùng điều kiện > khi so sánh.

In-place (dùng O(1) bộ nhớ thêm).

Adaptive: nhanh khi dữ liệu đã gần như sắp xếp.

Online: có thể tiếp nhận phần tử mới và chèn ngay (thích hợp cho stream).

6. Ưu điểm

Mã đơn giản, dễ hiểu và triển khai.

Rất hiệu quả cho mảng nhỏ (ví dụ n ≤ 20–50, tuỳ thực thi).

Rất tốt khi dữ liệu gần như đã sắp xếp (chạy gần O(n)).

Ổn định và in-place.

Thích hợp làm base case cho các thuật toán chia để trị (merge sort / quicksort) — chuyển sang insertion sort khi phần tử ít.

7. Nhược điểm

Kém với mảng lớn và ngẫu nhiên (O(n²) tệ).

Dịch phần tử (shifts) nhiều lần — chi phí di chuyển cao nếu phần tử nặng.

Không tận dụng được tính song song tốt.

8. Khi nào dùng / không dùng

Dùng khi:

- n nhỏ (ví dụ: trong base-case của quicksort/mergesort).

- Dữ liệu gần sắp xếp (ít xáo trộn).

- Cần sắp xếp online (nhận phần tử dần dần).

- Cần thuật toán ổn định + đơn giản.

Không nên dùng khi:

- Dữ liệu lớn và ngẫu nhiên (dùng quicksort/mergesort/Heapsort).

- Khi di chuyển phần tử rất tốn kém (ví dụ phần tử rất lớn hoặc sao chép đắt tiền) — cân nhắc dùng cấu trúc liên kết hoặc thuật toán khác.

9. Biến thể & tối ưu

Binary insertion sort: dùng tìm kiếm nhị phân để tìm vị trí chèn → giảm số so sánh xuống O(n log n) nhưng vẫn phải dịch phần tử → tổng O(n²) về di chuyển.

Insertion sort trên linked list: tìm vị trí O(n), nhưng chèn O(1) (không cần dịch), vẫn tổng O(n²).

Kết hợp: thường dùng insertion sort cho các subarray nhỏ trong mergesort/quicksort/timsort.

10. Ứng dụng thực tế

Làm base case cho các thuật toán sắp xếp lai (tối ưu thực thi cho n nhỏ).

Sắp xếp các tập dữ liệu gần như đã sắp xếp (log file gần thứ tự thời gian, danh sách gần đúng).

Khi cần thêm phần tử vào bộ sắp xếp liên tục (online).

Sắp xếp các danh sách ngắn trong code nhúng, nơi bộ nhớ hạn chế.

23/09/2025

[Bản tin - 2] Các nhà nghiên cứu tùy chỉnh công cụ AI tại ‘hackathon’ toàn cầu
Hơn 1200 nhà khoa học và lập trình viên khám phá cách mô hình ngôn ngữ lớn có thể được ứng dụng trong khoa học vật liệu và hóa học

---

BERLIN – Năm 2023, khi gia đình của Ben Blaiszik đi nghỉ, anh đã làm điều mà bất kỳ nhà khoa học dữ liệu nào cũng có thể làm khi có một cuối tuần rảnh: tổ chức một hackathon toàn cầu. Blaiszik, vốn được đào tạo trong lĩnh vực khoa học vật liệu nhưng hiện làm việc về học máy tại Đại học Chicago, cảm nhận rằng trí tuệ nhân tạo (AI) đang trên đà thay đổi lĩnh vực cũ của mình. “Tôi có thể thấy điều đó hiển hiện trước mắt,” anh nói. “Nhưng chúng ta chưa thực sự khám phá mảnh đất này.” Thế là anh quyết định thúc đẩy tiến trình bằng một cuộc thi thân thiện.

Tuần trước, lần tổ chức thứ ba của hackathon do Blaiszik khởi xướng đã thu hút hơn 1200 nhà nghiên cứu và lập trình viên từ khắp nơi trên thế giới. Trong suốt 48 giờ cùng vô số phần pizza, các nhóm tham gia trực tuyến và tại các điểm tổ chức trực tiếp đã cùng nhau khai thác sức mạnh của các công cụ được gọi là mô hình ngôn ngữ lớn (LLM) trong khoa học vật liệu và khám phá thuốc. Cạnh tranh cho những giải thưởng tiền mặt nhỏ, hơn 100 đội đã nộp video dài 2 phút để trình bày dự án—một số trông chẳng khác gì trailer Pixar giả lập chuyên nghiệp. Tất cả các bài dự thi đang được tập hợp thành một bài báo để minh họa sự đa dạng của các ứng dụng AI tiềm năng, từ việc tạo giả thuyết đến quản lý dữ liệu và dự đoán tính chất vật liệu. Các bài dự thi cũng làm nổi bật một thách thức then chốt: xây dựng các quy trình chuyên biệt để thu thập và chuẩn hóa dữ liệu nhằm biến một LLM thành công cụ nghiên cứu tùy chỉnh.

“Sự kiện này thực sự là một chất xúc tác cho những ý tưởng tuyệt vời,” Pepe Márquez, nhà khoa học vật liệu tại Đại học Humboldt, người tổ chức điểm thi đấu ở Berlin, cho biết. “Đây là cơ hội để mọi người tạm dừng công việc thường ngày và có sự tự do để thử nghiệm với các công cụ mới.”

LLM như ChatGPT của OpenAI hoạt động bằng cách hấp thụ khối lượng khổng lồ dữ liệu trực tuyến và sử dụng các mẫu được nhận diện để tạo ra chuỗi văn bản có tính hợp lý nhằm phản hồi đầu vào. Các mô hình này đã mở ra cánh cửa mới trong nghiên cứu khoa học, cho phép các nhà nghiên cứu rà soát tài liệu và “giải phóng dữ liệu bị mắc kẹt trong các bài báo” ở quy mô chưa từng có, Blaiszik nói. Nhưng ở trạng thái nguyên bản, LLM không phải lúc nào cũng là cộng sự phòng thí nghiệm đáng tin cậy. Chúng cần được điều chỉnh và tinh chỉnh để làm việc với những loại dữ liệu khoa học cụ thể—điều này đòi hỏi sự hợp tác liên ngành giữa các chuyên gia.

Chưa từng có kinh nghiệm với LLM, nghiên cứu sinh tiến sĩ vật lý Daniel Speckhard tại Humboldt đã lập nhóm cùng một nhà khoa học dữ liệu, một nhà khoa học máy tính, và một nhà toán học. Họ đặt mục tiêu kiểm tra khả năng của LLM trong việc dự đoán cách cấu trúc tinh thể của một vật liệu “thư giãn” về cấu hình năng lượng thấp nhất—một bước quan trọng để dự đoán tính chất của nó. Họ tinh chỉnh một LLM sẵn có, mô hình T5 của Google AI, bằng cách đưa vào dữ liệu tinh thể học chứa các ví dụ về cấu trúc tinh thể ở các mức năng lượng khác nhau. Sau đó, họ yêu cầu mô hình dự đoán cách một tinh thể mới sẽ thư giãn—chỉ dựa trên các mẫu trong dữ liệu đã thấy, không dùng bất kỳ lý thuyết vật lý nền tảng nào. Dù nhóm chỉ có thời gian huấn luyện mô hình trên một tập dữ liệu nhỏ, kết quả ban đầu khá khả quan, Speckhard cho biết.

Ấn tượng hơn khả năng đoán hành vi tinh thể phức tạp của mô hình, theo Speckhard, là việc nó dễ dàng được tùy chỉnh đến mức nào. Bằng cách nhờ các LLM khác hỗ trợ viết mã nhập và phân tích dữ liệu, nhóm đã hoàn thành trong 2 ngày những việc mà Speckhard sẽ phải mất hơn một tháng. Giờ đây anh xem LLM như một cộng sự đầy hứa hẹn trong nghiên cứu. Trước sự kiện, “tôi nghĩ chúng lấy đi hết niềm vui của khoa học—tôi muốn tự mình tiếp cận vấn đề,” anh nói. “Nhưng sau trải nghiệm này, tôi tin tưởng 100%.”

Một số đội hackathon khác thiết kế các tác tử tùy chỉnh—bao gồm một công cụ hỗ trợ giải quyết vấn đề kiểm soát chất lượng lâu đời trong sản xuất thuốc và vật liệu: biết nguyên liệu được sản xuất ở đâu và khi nào. Bằng cách trích xuất thông tin từ các tài liệu rải rác, tác tử AI có thể tạo một thẻ kỹ thuật số duy nhất để theo dõi chuỗi cung ứng thuốc trong trường hợp cần thu hồi vì an toàn. Những đội khác cho thấy cách các LLM nguồn mở hiện có có thể giúp thiết kế thuốc mới sau khi được đưa vào dữ liệu như cấu trúc 3D của các phân tử, rồi được huấn luyện để dự đoán hóa chất nào cần tổng hợp. Một đội khác xây dựng một chatbot “đồng phi công” kết hợp các công cụ AI sẵn có cho hóa học để giúp các nhà khoa học tạo giả thuyết nghiên cứu mới.

Márquez tin rằng AI có thể tăng tốc mạnh mẽ quá trình khám phá vật liệu, vốn hiện nay là một quy trình cồng kềnh dựa vào “trực giác hóa học, những gì bạn đọc được trong bài báo, hoặc những gì bạn có sẵn trong phòng thí nghiệm.” Nhưng dữ liệu huấn luyện cần thiết để tinh chỉnh công cụ thường khó tìm hoặc không sử dụng được. Một giải pháp là nền tảng NOMAD, do Márquez và đồng nghiệp phát triển trong thập kỷ qua, hiện là kho dữ liệu khoa học vật liệu tập trung lớn nhất, với hơn 19 triệu mục nhập cộng đồng cho hơn 4 triệu vật liệu. Tại hackathon ở Berlin, một số đội đã thiết kế chatbot để hướng dẫn các nhà khoa học sử dụng NOMAD, trong khi những đội khác xây dựng các quy trình trích xuất dữ liệu để tự động đưa kết quả phòng thí nghiệm vào cơ sở dữ liệu NOMAD.

Ana Velázquez, làm việc tại Helmholtz-Zentrum Berlin—một viện nghiên cứu công nghệ năng lượng—với vai trò “người quản lý dữ liệu” (data steward), đang hỗ trợ các nhà khoa học khai thác NOMAD. “Công việc của tôi là giúp việc số hóa trở nên dễ dàng hơn cho các nhà khoa học,” cô nói. Cô phối hợp với các nhà hóa học và vật lý để đánh giá cách AI có thể tăng tốc quy trình và phát triển các thiết lập NOMAD tùy chỉnh để tự động hóa phân tích dữ liệu. “Khi mọi thứ đã sẵn sàng, họ chỉ cần kéo-thả một tệp, và mọi thứ sẽ như phép màu với họ.”

Hiện nay, 32 giám khảo chuyên môn từ các viện nghiên cứu và tập đoàn đang xem xét các bài dự thi. Blaiszik dự định kết nối các đội thắng giải với các cố vấn và quỹ đầu tư mạo hiểm để giúp phát triển nguyên mẫu thành sản phẩm hoàn chỉnh. Nhưng ngay cả với những người sẽ không tiếp tục dự án, hackathon vẫn khuyến khích một điều ngày càng quý giá trong thời đại AI: làm việc nhóm. “Nguy cơ của AI là nó cho phép chúng ta làm quá nhiều mà không cần hợp tác với ai,” Kutlualp Tazefidan, một lập trình viên tại Viện Nghiên cứu và Thử nghiệm Vật liệu Liên bang Đức, người đã tham gia phát triển ứng dụng kiểm soát chất lượng, nói. “Chúng ta thực sự cần nhiều sự kiện như thế này hơn.”

Ngay sau đó, một đồng đội của anh, do tụt đường huyết sau khi ăn quá nhiều bánh ngọt, nói rằng não cô mờ mịt đến mức khó hoàn thành bản báo cáo. “Không sao đâu,” Tazefidan nói. “Tôi sẽ chỉ nhờ ChatGPT.”

------
Nguồn: Researchers customize AI tools at global ‘hackathon’ (19/09/2025)

Tay Ninh Algorithm Group

25/11/2025

25/11/2025

25/11/2025

25/11/2025

25/11/2025

25/11/2025

25/11/2025

27/09/2025

27/09/2025

23/09/2025

Address

Website

Alerts

Shortcuts

Share

Category

Listing takedown request