Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Article by Loser1 – Learning AI with Losers
Các bạn nên đọc và nắm vững 2 phần lý thuyết trước khi bắt đầu làm bài tập nhé! Để đảm bảo không bỏ lỡ kiến thức quan trọng, hãy đọc theo thứ tự:
Chào các bạn, lại là loser1 From Learning AI with losers đây ! Sau khi đã cùng nhau băng qua “khu rừng” lý thuyết với hai phần về nền tảng cơ bản và phân tích độ phức tạp, đã đến lúc chúng ta thực sự “getting our hands dirty” với những bài tập thực tế rồi! 💪
Để đảm bảo chất lượng và tính thực tiễn, mình đã tổng hợp các bài tập từ nguồn “xịn sò” nhất có thể – đó là đề thi của các trường đại học hàng đầu về công nghệ tại Việt Nam:
Tại sao lại chọn các bài tập này? Bởi vì:
Mỗi bài tập sẽ được trình bày theo format sau:
Được rồi, giờ thì… Let’s crush some algorithms! 🚀
Phần 0 : Nền Tảng
Ưu và nhược điểm của kiến trúc dữ liệu động
Ưu điểm:
Nhược điểm:
a. Heapsort: O(nlogn) với n là số phần tử của mảng cần sắp thứ tự
b. Mergesort: O(nlogn) với n là số phần tử của mảng cần sắp thứ tự
c. Quicksort: O(n²) trong trường hợp xấu nhất, O(n log n) trong trường hợp trung bình và tốt nhất
d. Counting Sort: O(n + k) (với n là số phần tử và k là giá trị lớn nhất trong mảng)
e. Sequential Search: O(n) trong trường hợp trung bình với xấu nhất, O(1) trong trường hợp tốt nhất (với n là số phần tử)
f. Tìm kiếm nhị phân (Binary Search): O(log n) trong trường hợp trung bình với xấu nhất, O(1) trong trường hợp tốt nhất (với n là số phần tử)
g. Naive: O(n*m) trong trường hợp trung bình với xấu nhất, O(n) trong trường hợp tốt nhất
h. KMP: O(n + m): Với n là độ dài của chuỗi văn bản và m là độ dài của chuỗi mẫu
i. Xây dựng BST từ mảng sắp xếp tăng: O(n) với n là số phần tử
j. Tìm kiếm trong hash table trong trường hợp không có đụng độ xảy ra: O(1)
Đề 2:
Đề 3:
Gọi Số phần tử của A1, A2, A3 là n1, n2, n3
Cứ insert lần lượt phần tử vô cây nhị phân của A1, A2, A3
Độ phức tạp: O(NlogN) với N = n1 + n2 + n3 (cả 3 trường hợp tệ, trung bình, tốt nhất)
Đầu tiên ta sẽ ghép 3 mảng lại với nhau lần lượt bằng thuật toán 2 con trỏ:
Chi Phí:
Tổng chi phí O(N + LogN) = O(N) hay O(n) thỏa yêu cầu đề bài
Ghép mảng 2 con trỏ: O(N)
Từ mảng tăng dần chuyển sang BST: O(LogN)
Không hiểu sao bắt đầu từ 1 kết thúc ở X.length mà không phải là từ 0 tới X.length-1
Giả sử 0 tới X.length:
// Hàm heapify giúp xây dựng heap từ mảng
void heapify(vector<int>& X, int n, int i) {
int smallest = i;
int left = 2 * i + 1; // chỉ số con trái
int right = 2 * i + 2; // chỉ số con phải
if (left < n && X[left] < X[smallest])
smallest = left;
if (right < n && X[right] < X[smallest])
smallest = right;
if (smallest != i) {
swap(X[i], X[smallest]);
heapify(X, n, smallest);
}
}
// Hàm Heapsort để sắp xếp mảng X
void Heapsort(vector<int>& X) {
int n = X.size();
// Xây dựng heap từ giữa mảng trở về đầu
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(X, n, i);
}
// Lấy phần tử lớn nhất (root) ra và heapify lại mảng
for (int i = n - 1; i > 0; i--) {
swap(X[0], X[i]); // Di chuyển phần tử lớn nhất về cuối
heapify(X, i, 0); // Heapify lại mảng chưa sắp xếp
}
}
// Hàm Better_A tính khoảng cách nhỏ nhất giữa các phần tử liên tiếp sau khi sắp xếp
int Better_A(vector<int>& X) {
Heapsort(X); // Sắp xếp mảng X bằng Heapsort
int d = INT_MAX; // Khởi tạo d với giá trị vô cùng (INT_MAX)
// Duyệt qua các phần tử liên tiếp trong mảng đã sắp xếp
for (int i = 0; i < X.size() - 1; i++) {
int diff = abs(X[i] - X[i + 1]); // Tính hiệu giữa 2 phần tử liên tiếp
if (diff < d) {
d = diff; // Cập nhật khoảng cách nhỏ nhất
}
}
return d; // Trả về khoảng cách nhỏ nhất
}
Time complexity: O(nlogn + n) = O(nlogn)
Space complexity: O(n)
với n là số phần tử trong mảng X
Lưu ý:
Thuật toán sử dụng hai vòng lặp lồng nhau:
Trường hợp xấu nhất:
Trường hợp tốt nhất:
Trường hợp trung bình:
Trường hợp | Độ phức tạp |
---|---|
Tốt nhất | O(n) |
Xấu nhất/Trung bình | O(n * m) |
t, h, k, t, j, i thật sự không ảnh hưởng gì tới độ phức tạp thuật toán tại nó không ảnh hướng tới n.
(n−i)+1
n−n+1 = 1
Do a với b không ảnh hưởng tới loop dừng khi nào nên:
Chạy tay với a = 5, b = 7:
a | b | Trả về |
---|---|---|
5 | 7 | return 7 + 2 * 14 = 35 (kết quả cuối cùng) |
2 | 7 | return 2*7 = 14 |
1 | 7 | return 7 + 2*0 = 7 |
0 | 7 | return 0 |
Kết luận:
Hàm fast power dùng phương pháp chia để trị để tính lũy thừa x^n. Tuy nhiên cách triển khai hiện tại không tối ưu do gọi đệ quy hai lần cùng một giá trị n/2, dẫn đến phải tính toán lặp đi lặp lại.
Với mỗi lần gọi, hàm tạo ra 2 lần đệ quy với n/2:
Làm sao để tối ưu?
Tôi sẽ định dạng lại nội dung cho WordPress và sửa các lỗi nhỏ (nếu có):
Cuối cùng dùng công thức nhân: O((m+n)*m)
Vậy tổng số lần thực hiện hay S+=1 được gọi là 10*(1+2+…+10)
Bài này gặp rồi, tương tự thôi.
Có thể sai đề: tại ngay vòng while, j– không thấy ràng buộc j > 0 nên j có thể âm vô lý.
Ta sẽ giải theo đề đã sửa:
Ký hiệu Big-O: O(n)
Giải thích:
Nếu thuật toán sắp xếp O(n log n) (như merge, heap sort):
Nếu thuật toán sắp xếp O(n²) (như interchange, insertion sort):
Còn counting sort thì:
Câu 7 : Độ phức tạp là O(n^3)
Câu 8 :
Lời giải: Để so sánh các độ phức tạp, ta xếp theo thứ tự tăng dần: O(nlogn) < O(n⁴) < O(2ⁿ) < O(n!)
Vậy O(n!) là độ phức tạp lớn nhất.
Câu 9 : Định Nghĩa :
Bubble Sort là thuật toán sắp xếp đơn giản:
Khi thêm một phần tử vào mảng, độ phức tạp phụ thuộc vào vị trí chèn:
Phân tích chi tiết:
Phân tích:
Phân tích:
Trong đó n là số phần tử của mảng. Độ phức tạp không gian là O(1) vì chỉ cần một số biến phụ trợ cố định.
Đoạn code có 3 vòng lặp lồng nhau:
for (i = 1; i ≤ n; i++)
for (j = 1; j ≤ i * i; j++)
for (k = 1; k ≤ j; k++)
sum++;
Để tính số lần thực hiện phép toán sum++, ta cần phân tích từ trong ra ngoài:
Vòng lặp k chạy từ 1 đến j:
for (k = 1; k ≤ j; k++)
sum++;
Số lần thực hiện = j
Vòng lặp j chạy từ 1 đến i*i:
for (j = 1; j ≤ i * i; j++)
Với mỗi j, ta có j lần thực hiện từ vòng lặp k.
Tổng số lần thực hiện = 1 + 2 + 3 + … + (i * i) = (i*i)(i*i + 1)/2 = (i⁴ + i²)/2
Vòng lặp i chạy từ 1 đến n:
for (i = 1; i ≤ n; i++)
Với mỗi i, ta có (i⁴ + i²)/2 lần thực hiện từ hai vòng lặp trong.
Tổng số phép toán = ∑(i=1 đến n) (i⁴ + i²)/2
= (1/2)[∑(i=1 đến n) i⁴ + ∑(i=1 đến n) i²]
Theo chú ý: ∑(i=1 đến n) i^k ≈ (n^(k+1))/(k+1)
Áp dụng cho i⁴:
Áp dụng cho i²:
Tổng số phép toán = (1/2)[n⁵/5 + n³/3]
= (n⁵/10 + n³/6)
Do n⁵ là số hạng có bậc cao nhất, nên độ phức tạp của thuật toán là O(n⁵).
Vì vậy, ta có thể bỏ qua các số hạng có bậc thấp hơn và kết luận độ phức tạp là O(n⁵)
Khi n lớn, số hạng n⁵ sẽ chiếm ưu thế và lớn hơn rất nhiều so với n³
Các hệ số như 1/10 không ảnh hưởng đến ký hiệu Big-O
Tôi sẽ phân tích độ phức tạp trong trường hợp xấu nhất cho từng công việc:
Độ phức tạp: O(N)
Giải thích: Để kiểm tra max-heap, ta cần duyệt qua tất cả các nút và so sánh với các nút con. Mỗi phần tử cần được kiểm tra một lần, nên ta cần duyệt qua N phần tử.
Độ phức tạp: O(N)
Giải thích: Ta cần duyệt qua toàn bộ dãy và so sánh từng cặp phần tử liền kề để đảm bảo a[i] ≤ a[i+1]. Việc này đòi hỏi duyệt qua N phần tử một lần.
Độ phức tạp: O(1)
Giải thích: Truy cập trực tiếp vào phần tử cuối cùng của mảng chỉ cần một phép toán, không phụ thuộc vào kích thước mảng.
Độ phức tạp: O(N)
Giải thích: Trong trường hợp xấu nhất của hàng đợi dùng mảng, khi lấy phần tử đầu ra, ta phải dịch chuyển tất cả các phần tử còn lại lên một vị trí.
Độ phức tạp: O(N)
Giải thích: Trong trường hợp xấu nhất, cây bị suy biến thành một đường thẳng, ta phải duyệt qua tất cả N phần tử.
Độ phức tạp: O(N)
Giải thích: Trong trường hợp xấu nhất, phần tử cần xóa nằm ở cuối danh sách, ta phải duyệt từ đầu đến cuối danh sách để tìm và xóa nó.
Độ phức tạp: O(N)
Giải thích: Ta cần duyệt qua tất cả các nút của cây để tìm và hiển thị các khóa chẵn. Trong trường hợp xấu nhất, ta phải thăm tất cả N nút.
Độ phức tạp: O(N)
Giải thích: Trong max-heap, phần tử nhỏ nhất luôn nằm ở các nút lá. Để tìm phần tử nhỏ nhất, ta cần duyệt qua tất cả các nút lá và so sánh chúng, điều này đòi hỏi việc kiểm tra tất cả N phần tử trong trường hợp xấu nhất.
Loser1 sẽ giúp bạn giải quyết bài toán sắp xếp chậu cây này một cách chi tiết. Hãy cùng phân tích từng bước:
Bước 1: Phân tích yêu cầu bài toán
Bước 2: Xác định phương pháp giải quyết
Để tối ưu quãng đường di chuyển, ta có thể áp dụng phương pháp “Sắp xếp tại chỗ”. Điều này có nghĩa là:
Bước 3: Thuật toán cụ thể
Bước 4: Ví dụ minh họa
Giả sử có 5 chậu cây với chiều cao (đơn vị cm): 30, 15, 25, 10, 20
Vị trí ban đầu: [30] [15] [25] [10] [20]
Vị trí cần đến: [10] [15] [20] [25] [30]
Các bước hoán đổi:
Bước 5: Kết luận
Phương pháp này đảm bảo:
Đây là cách sắp xếp tối ưu nhất vì nó kết hợp được hai yếu tố:
Quảng đường di chuyển các chậu là ngắn nhất -> số lần di chuyển ít nhất -> selection sort
Loser1 sẽ giải thích thuật toán Knuth-Morris-Pratt (KMP) thông qua code C++ và phân tích độ phức tạp của nó:
// Thuật toán KMP dùng để tìm kiếm mẫu P trong chuỗi văn bản T
void computeLPSArray(string pattern, int M, int* lps) {
int len = 0; // Độ dài của tiền tố-hậu tố trùng nhau trước đó
lps[0] = 0; // lps[0] luôn bằng 0
int i = 1;
while (i < M) {
if (pattern[i] == pattern[len]) {
len++;
lps[i] = len;
i++;
}
else {
if (len != 0) {
len = lps[len - 1];
}
else {
lps[i] = 0;
i++;
}
}
}
}
void KMPSearch(string pattern, string text) {
int M = pattern.length();
int N = text.length();
// Tạo mảng lps[] để lưu độ dài tiền tố-hậu tố dài nhất
int lps[M];
computeLPSArray(pattern, M, lps);
int i = 0; // index cho text
int j = 0; // index cho pattern
while (i < N) {
if (pattern[j] == text[i]) {
j++;
i++;
}
if (j == M) {
cout << "Tìm thấy mẫu tại vị trí " << i - j << endl;
j = lps[j - 1];
}
else if (i < N && pattern[j] != text[i]) {
if (j != 0)
j = lps[j - 1];
else
i++;
}
}
}
KMP là một ví dụ điển hình về cách cải thiện độ phức tạp thời gian bằng cách sử dụng thêm một chút bộ nhớ và tiền xử lý thông minh.