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
Chào mừng các bạn đến với series “Chinh Phục DSA – Từ Cơ Bản Đến Nâng Cao”, nơi chúng ta sẽ cùng nhau khám phá những kiến thức về Cấu Trúc Dữ Liệu và Thuật Toán (DSA). Đây là nền tảng không thể thiếu đối với những ai đam mê lập trình và khoa học máy tính.
Series này dành cho ai?
Bạn sẽ học được gì?
Hôm nay, chúng ta sẽ bắt đầu với Phần 1: Nền Tảng và Độ Phức Tạp Thuật Toán, nơi mình chia sẻ cách tiếp cận phân tích và đánh giá hiệu suất thuật toán từ những khái niệm cơ bản nhất.
Khái niệm cơ bản:
Tầm quan trọng:
Hãy xem một ví dụ cụ thể để hiểu rõ hơn:
# Cách 1: Tìm số lớn nhất trong mảng
def find_max_v1(arr):
max_val = arr[0]
for i in range(len(arr)):
for j in range(len(arr)):
if arr[j] > max_val:
max_val = arr[j]
return max_val
# Cách 2: Tìm số lớn nhất trong mảng
def find_max_v2(arr):
max_val = arr[0]
for num in arr:
if num > max_val:
max_val = num
return max_val
Cả 2 cách đều cho kết quả chính xác. Nhưng:
→ Đây chính là lý do chúng ta cần phân tích thuật toán!
Trong bài này, chúng ta sẽ tập trung vào phân tích thời gian thực hiện.
Dưới đây là phần giải thích chi tiết về Phân Tích Độ Phức Tạp Thời Gian, được mở rộng và dễ hiểu cho người mới bắt đầu (beginner):
Khi chúng ta nói về độ phức tạp thời gian của một thuật toán, T(n) chính là hàm mô tả thời gian chạy của thuật toán đó, với n
là kích thước của input (dữ liệu đầu vào).
Hàm thời gian T(n) cho ta biết rằng:
n
) thay đổi, thuật toán sẽ mất bao lâu để xử lý hết tất cả.int getFirst(int arr[], int n) {
return arr[0]; // Trả về phần tử đầu tiên
}
int getSum(int arr[], int n) {
int sum = 0; // C3
for(int i = 0; i < n; i++) { // Lặp n lần
sum += arr[i]; // C2
}
return sum;
}
void printPairs(int arr[], int n) {
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
cout << arr[i] << "," << arr[j] << endl;
}
}
}
Khi tính toán độ phức tạp thời gian của một thuật toán phức tạp, chúng ta sẽ sử dụng một số quy tắc cơ bản:
Quy tắc cộng dùng khi thuật toán có nhiều đoạn mã (blocks) độc lập nhau, và mỗi đoạn có độ phức tạp riêng biệt. Thời gian chạy tổng của thuật toán là tổng thời gian của các đoạn mã này.
Công thức: T(n) = T1(n) + T2(n) + ... + Tk(n)
→ Độ phức tạp tổng là O(max(T1(n), T2(n), …, Tk(n))).
void function(int arr[], int n) {
// Block 1: O(n)
for(int i = 0; i < n; i++) {
cout << arr[i];
}
// Block 2: O(n^2)
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
cout << arr[i] + arr[j];
}
}
}
// T(n) = O(n) + O(n^2) = O(max(n, n^2)) = O(n^2)
Quy tắc nhân dùng khi thuật toán có các vòng lặp lồng nhau (nested loops) hoặc khi hai phần của thuật toán phụ thuộc vào nhau.
Công thức: T(n) = T1(n) * T2(n) * ... * Tk(n)
.
void function(int arr[], int n) {
// Vòng for ngoài: O(n)
for(int i = 0; i < n; i++) {
// Vòng for trong: O(n)
for(int j = 0; j < n; j++) {
cout << arr[i] + arr[j];
}
}
}
// T(n) = O(n) * O(n) = O(n^2)
T(n) = 3n + 5
→ O(n), không ghi O(3n) hay O(5).T(n) = 2n² + 10n + 100
→ O(n²).n
rất lớn, các thành phần bậc thấp (như n
, hằng số) trở nên không đáng kể so với thành phần bậc cao (như n²
, n³
).n
).Hy vọng phần giải thích này giúp bạn dễ dàng hiểu và áp dụng khi phân tích độ phức tạp thời gian trong các bài toán thuật toán!
T(n) = O(f(n)) nếu tồn tại các hằng số c và n0 sao cho: T(n) ≤ c*f(n) với mọi n ≥ n0.
Ví dụ:
T(n) = 3n^2 + 2n + 1 = O(n^2)
T(n) = n^3 + 1000n^2 = O(n^3)
T(n) = 2^n + n^100 = O(2^n)
Độ phức tạp O(1) có nghĩa là thời gian thực thi của thuật toán là cố định, không phụ thuộc vào kích thước của dữ liệu đầu vào. Điều này có nghĩa là bất kể kích thước mảng là bao nhiêu, thuật toán sẽ thực hiện trong thời gian cố định.
int getFirstElement(int arr[]) {
return arr[0]; // Lấy phần tử đầu tiên trong mảng
}
Độ phức tạp O(n) có nghĩa là thời gian thực thi sẽ tăng tỷ lệ thuận với kích thước của dữ liệu đầu vào. Mỗi phần tử trong mảng hoặc danh sách phải được duyệt qua một lần.
int sumArray(int arr[], int n) {
int sum = 0;
for(int i = 0; i < n; i++) {
sum += arr[i]; // Cộng dồn tất cả phần tử trong mảng
}
return sum;
}
Độ phức tạp O(n^2) xảy ra khi thuật toán phải lặp qua mảng và với mỗi phần tử, lại lặp qua một mảng con khác. Điều này làm cho số bước thực hiện tăng theo bình phương số phần tử trong mảng.
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n-1; i++) {
for (int j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]) {
swap(arr[j], arr[j+1]); // Đổi chỗ nếu sai thứ tự
}
}
}
}
Độ phức tạp O(log n) xảy ra khi thuật toán loại bỏ một nửa dữ liệu mỗi lần thực hiện. Đây là độ phức tạp điển hình của các thuật toán tìm kiếm nhị phân.
int binarySearch(int arr[], int n, int x) {
int left = 0, right = n-1;
while(left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == x) return mid;
if (arr[mid] < x) left = mid + 1;
else right = mid - 1;
}
return -1; // Nếu không tìm thấy
}
Độ phức tạp O(n log n) thường xuất hiện trong các thuật toán sắp xếp hiệu quả, như sắp xếp trộn (Merge Sort) hoặc sắp xếp nhanh (Quick Sort).
void merge(int arr[], int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[l + i];
for (int i = 0; i < n2; i++)
R[i] = arr[m + 1 + i];
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j])
arr[k++] = L[i++];
else
arr[k++] = R[j++];
}
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m); // Sắp xếp nửa trái
mergeSort(arr, m + 1, r); // Sắp xếp nửa phải
merge(arr, l, m, r); // Gộp lại
}
}
Độ phức tạp O(2^n) xuất hiện khi thuật toán phải thực hiện một số lượng bước gấp đôi với mỗi phần tử bổ sung. Đây là độ phức tạp phổ biến trong các thuật toán đệ quy không hiệu quả, chẳng hạn như bài toán nhị phân.
int fibonacci(int n) {
if (n <= 1) return n;
return fibonacci(n-1) + fibonacci(n-2); // Tính dãy Fibonacci
}
So sánh độ phức tạp:
Độ phức tạp | n=10 | n=100 | n=1000 |
---|---|---|---|
O(1) | 1 | 1 | 1 |
O(log n) | 3.32 | 6.64 | 9.97 |
O(n) | 10 | 100 | 1000 |
O(n log n) | 33.2 | 664 | 9970 |
O(n²) | 100 | 10000 | 1000000 |
O(2ⁿ) | 1024 | 2¹⁰⁰ | 2¹⁰⁰⁰ |
Phân tích độ phức tạp thời gian của các cấu trúc lập trình giúp xác định cách thuật toán hoạt động dựa trên kích thước đầu vào n
. Dưới đây là hướng dẫn chi tiết từng cấu trúc:
n
. int a = 5; // O(1) - Gán giá trị
cout << "Hello"; // O(1) - In ra màn hình
int sum = a + b; // O(1) - Phép tính số học
arr[i] = x; // O(1) - Truy cập/gán mảng
return value; // O(1) - Trả về giá trị
n
lớn hay nhỏ, các câu lệnh này chỉ thực hiện một lần và tốn thời gian cố định.T(n) = max(T_then(n), T_else(n))
if (arr[0] > arr[1]) { // O(1) - Kiểm tra điều kiện
// Nhánh 1: O(n)
for(int i = 0; i < n; i++) {
cout << arr[i];
}
} else {
// Nhánh 2: O(n²)
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
cout << arr[i] + arr[j];
}
}
}
T(n) = max(O(n), O(n²)) = O(n²)
. switch(value) {
case 1:
for(int i = 0; i < n; i++) { // O(n)
cout << i;
}
break;
case 2:
cout << "Hello"; // O(1)
break;
default:
for(int i = 0; i < n; i++) { // O(n)
for(int j = 0; j < n; j++) {
cout << i + j;
}
}
}
T(n) = max(O(n), O(1), O(n²)) = O(n²)
.T(n) = Số lần lặp * Độ phức tạp thân vòng lặp
. for(int i = 0; i < n; i++) { // n lần lặp
cout << arr[i]; // O(1) mỗi lần
}
→ T(n) = n * O(1) = O(n).
for(int i = 0; i < n; i++) { // n lần lặp
for(int j = 0; j < n; j++) { // n lần lặp mỗi i
cout << arr[i] + arr[j]; // O(1)
}
}
→ T(n) = n * n * O(1) = O(n²).
i += c
): for(int i = 1; i <= n; i += 2) { // Số lần lặp ≈ n/2
cout << i; // O(1)
}
→ T(n) = (n/2) * O(1) = O(n) (Bỏ qua hằng số).
i *= 2
): for(int i = 1; i <= n; i *= 2) { // Số lần lặp = log2(n)
cout << i; // O(1)
}
→ T(n) = log2(n) * O(1) = O(log n).
for(int i = 0; i < n; i++) { // n lần
for(int j = 0; j < m; j++) { // m lần
cout << i + j; // O(1)
}
}
→ T(n, m) = n * m * O(1) = O(n*m).
for(int i = 0; i < n; i++) {
for(int j = i; j < n; j++) { // Số lần lặp giảm dần
cout << i + j; // O(1)
}
}
i = 0
: j chạy từ 0 đến n-1 → n lần.i = 1
: j chạy từ 1 đến n-1 → n-1 lần.n + (n-1) + (n-2) + ... + 1 = n(n+1)/2
.Đệ quy là một kỹ thuật trong lập trình, trong đó hàm gọi chính nó để giải quyết vấn đề nhỏ hơn của chính nó. Quá trình này lặp đi lặp lại cho đến khi đạt được điều kiện dừng (base case).
Để tính giai thừa của một số n (ký hiệu là n!), chúng ta có thể sử dụng công thức sau: n!=n×(n−1)!
Với điều kiện dừng là: 1!= 1
Ví dụ về mã nguồn:
int factorial(int n) {
if(n <= 1) return 1; // Điều kiện dừng: O(1)
return n * factorial(n-1); // Gọi đệ quy
}
factorial
tính giai thừa của một số n.Bây giờ, chúng ta sẽ phân tích thời gian chạy của hàm đệ quy này.
factorial(n)
sẽ gọi đệ quy một lần nữa với factorial(n-1)
.Đệ quy chia để trị là một kỹ thuật đệ quy phổ biến trong các thuật toán như Merge Sort. Trong đệ quy chia để trị, chúng ta chia vấn đề thành các phần nhỏ hơn và giải quyết từng phần.
Merge Sort là một thuật toán sắp xếp sử dụng đệ quy chia để trị. Cách hoạt động của Merge Sort là:
Đây là mã nguồn của thuật toán Merge Sort:
void mergeSort(int arr[], int l, int r) {
if(l >= r) return; // Điều kiện dừng: O(1)
int mid = (l + r)/2; // O(1)
mergeSort(arr, l, mid); // T(n/2)
mergeSort(arr, mid+1, r); // T(n/2)
merge(arr, l, mid, r); // O(n)
}
mergeSort
chia mảng thành hai phần và gọi đệ quy cho từng phần.merge
) sẽ mất O(n) thời gian.Hy vọng bạn đã hiểu rõ về các bước tạo công thức đệ quy và cách giải quyết chúng!
IV. Tổng Kết Độ Phức Tạp Các Thuật Toán Quan Trọng
// Bảng so sánh các thuật toán sắp xếp:
/*
+---------------+---------------+---------------+---------------+------------------+
| Algorithm | Best | Average | Worst | Space |
+---------------+---------------+---------------+---------------+------------------+
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) |
| Selection Sort| O(n²) | O(n²) | O(n²) | O(1) |
| Insertion Sort| O(n) | O(n²) | O(n²) | O(1) |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) |
| Counting Sort | O(n + k) | O(n + k) | O(n + k) | O(k) |
| Radix Sort | O(d*(n + k)) | O(d*(n + k)) | O(d*(n + k)) | O(n + k) |
+---------------+---------------+---------------+---------------+------------------+
*/
// Các đặc điểm quan trọng:
/*
1. Stable Sorting (giữ thứ tự tương đối):
- Bubble Sort
- Insertion Sort
- Merge Sort
- Counting Sort
- Radix Sort
2. In-place (không cần bộ nhớ phụ đáng kể):
- Bubble Sort
- Selection Sort
- Insertion Sort
- Quick Sort (với stack O(log n))
- Heap Sort
3. Comparison based:
- Bubble/Selection/Insertion Sort: O(n²)
- Quick/Merge/Heap Sort: O(n log n)
- Lower bound cho các thuật toán so sánh: Ω(n log n)
4. Non-comparison based:
- Counting Sort
- Radix Sort
- Bucket Sort
- Có thể đạt O(n) trong điều kiện đặc biệt
*/
/*
+------------------+---------------+---------------+------------------+
| Algorithm | Best | Average | Worst |
+------------------+---------------+---------------+------------------+
| Linear Search | O(1) | O(n) | O(n) |
| Binary Search | O(1) | O(log n) | O(log n) |
| Jump Search | O(1) | O(√n) | O(√n) |
| Interpolation | O(1) | O(log log n) | O(n) |
| Exponential | O(1) | O(log n) | O(log n) |
| Fibonacci | O(1) | O(log n) | O(log n) |
| Hash Table | O(1) | O(1) | O(n) |
+------------------+---------------+---------------+------------------+
*/
/*
Binary Search Tree Operations:
+------------------+---------------+---------------+------------------+
| Operation | Best | Average | Worst |
+------------------+---------------+---------------+------------------+
| Search | O(1) | O(log n) | O(n) |
| Insert | O(1) | O(log n) | O(n) |
| Delete | O(1) | O(log n) | O(n) |
| Min/Max | O(1) | O(log n) | O(n) |
| Predecessor | O(1) | O(log n) | O(n) |
| Successor | O(1) | O(log n) | O(n) |
| Space Complexity | O(n) | O(n) | O(n) |
+------------------+---------------+---------------+------------------+
AVL Tree Operations:
Tất cả operations đều là O(log n) trong mọi trường hợp!
*/
/*
+------------------+---------------+
| Operation | Time |
+------------------+---------------+
| Build Heap | O(n) |
| Insert | O(log n) |
| Delete | O(log n) |
| Extract Min/Max | O(log n) |
| Get Min/Max | O(1) |
| Heapify | O(log n) |
+------------------+---------------+
*/
/*
1. KMP Algorithm (Knuth-Morris-Pratt)
- Preprocessing: O(m)
- Matching: O(n)
- Space: O(m)
Trong đó n là độ dài text, m là độ dài pattern
2. Robin-Karp Algorithm
- Average và Best Case: O(n+m)
- Worst Case: O(nm)
- Space: O(1)
3. Boyer-Moore Algorithm
- Best Case: O(n/m)
- Average Case: O(n)
- Worst Case: O(nm)
- Space: O(1)
*/
/*
+------------------+---------------+---------------+------------------+
| Operation | Best | Average | Worst |
+------------------+---------------+---------------+------------------+
| Search | O(1) | O(1) | O(n) |
| Insert | O(1) | O(1) | O(n) |
| Delete | O(1) | O(1) | O(n) |
+------------------+---------------+---------------+------------------+
Collision Resolution:
1. Chaining
- Space: O(n + m) with n elements in m slots
- Load Factor α = n/m affects performance
2. Open Addressing
- Linear Probing
- Quadratic Probing
- Double Hashing
Performance degrades as load factor increases
*/
/*
+------------------+--------------------+------------------+
| Algorithm | Time Complexity | Space Complexity |
+------------------+--------------------+------------------+
| BFS | O(V + E) | O(V) |
| DFS | O(V + E) | O(V) |
| Dijkstra | O(V log V + E) | O(V) |
| Bellman-Ford | O(VE) | O(V) |
| Floyd-Warshall | O(V³) | O(V²) |
| Prim's | O(V log V + E) | O(V) |
| Kruskal's | O(E log E) | O(V) |
| Topological Sort | O(V + E) | O(V) |
+------------------+--------------------+------------------+
*/
- Vòng lặp: Nhân với số lần lặp
- Câu lệnh tuần tự: Lấy max
- Đệ quy: Viết công thức truy hồi
- Chọn cấu trúc dữ liệu phù hợp
- Tận dụng không gian để giảm thời gian
- Sử dụng kỹ thuật Two Pointers, Sliding Window
- Cache kết quả trung gian (Dynamic Programming)
- n ≤ 10: O(n!) có thể chấp nhận được
- n ≤ 100: O(n³) có thể chấp nhận được
- n ≤ 1000: O(n²) có thể chấp nhận được
- n ≤ 10⁶: O(n log n) hoặc O(n) là cần thiết
- n > 10⁶: O(n) hoặc tốt hơn là bắt buộc
Bài viết được viết bởi Loser1 từ Learning AI with Losers. Follow chúng tôi tại:
[Còn Tiếp Phần 2]
SLIDE THAM KHẢO
Loser1 tổng hợp một số đề từ hcmus để giải các bạn ! ở phần sau nha
[…] 📚 Phần 1: Nền Tảng Cơ Bản 📖 Phần 2: Kỹ Thuật Nâng Cao Table Of Contents […]
[…] tạp phổ biến như O(1), O(n), O(n²), O(log n)… Nếu bạn chưa đọc phần 1, hãy click vào đây để đọc trước […]
[…] 📚 Phần 1: Nền Tảng Lý thuyết […]