Physical Address

304 North Cardinal St.
Dorchester Center, MA 02124

DSA Từ A-Z: Day 1 – Nền Tảng Cơ Bản và Phân Tích Độ Phức Tạp (Lý Thuyết P2)

Article by Loser1 – Learning AI with Losers

Table Of Contents
  1. Lời Mở Đầu

Lời Mở Đầu

Chào các bạn losers, loser1 lại quay trở lại rồi đây! 👋

Ở phần 1, chúng ta đã cùng nhau tìm hiểu về những khái niệm nền tảng của DSA, từ việc tại sao phải học DSA cho đến cách phân tích độ phức tạp thời gian và các độ phức 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 nhé!

Trong phần 2 này, chúng ta sẽ đi sâu hơn vào những kỹ thuật phân tích nâng cao, đặc biệt là Master Theorem – một công cụ cực kỳ powerful để phân tích độ phức tạp của các thuật toán đệ quy. Không chỉ vậy, chúng ta còn sẽ khám phá:

  • Các kỹ thuật phân tích đệ quy chi tiết
  • Phương pháp phân tích Amortized (chi phí khấu hao)
  • Các case study thực tế về optimizing algorithms
  • Và nhiều kiến thức “ngon bổ rẻ” khác!

Như mình đã nói ở phần 1, việc hiểu rõ về phân tích độ phức tạp không chỉ giúp bạn pass được phỏng vấn, mà còn là kỹ năng quan trọng để trở thành một developer thực sự giỏi. Hãy cùng mình deep dive vào phần 2 này nhé!

Lưu ý: Bài viết này là một phần trong series DSA Từ A-Z của Learning AI With Losers. Để có trải nghiệm học tập tốt nhất, bạn nên đọc theo thứ tự các phần.

Let’s get started! 🚀

V. Kỹ Thuật Phân Tích Nâng Cao

1. Master Theorem (Định Lý Thầy)

1.1. Giới thiệu và Tầm Quan Trọng

Master Theorem là một công cụ mạnh mẽ trong việc phân tích độ phức tạp của các thuật toán đệ quy. Định lý này được phát triển bởi Jon Bentley, Dorothea Haken và James B. Saxe vào năm 1980, và đã trở thành một trong những công cụ quan trọng nhất trong việc phân tích thuật toán.

1.2. Cấu Trúc Cơ Bản

Định lý áp dụng cho các công thức đệ quy có dạng:

T(n) = aT(n/b) + f(n)

Trong đó:

  • T(n): thời gian chạy cho input có kích thước n
  • a: số lượng các bài toán con (phải ≥ 1)
  • b: hệ số chia kích thước của bài toán (phải > 1)
  • f(n): chi phí để chia bài toán và kết hợp kết quả

1.3. Ba Trường Hợp Chi Tiết

Trường Hợp 1: Chi phí chia/kết hợp nhỏ hơn

Nếu f(n) = O(n^(log_b a - ε)) với ε > 0
T(n) = Θ(n^(log_b a))

Ví dụ minh họa:

C++
// Binary Tree Traversal
T(n) = 2T(n/2) + O(1)
// a = 2, b = 2, f(n) = 1
// n^(log_2 2) = n
// 1 = O(n^(1-ε))
// → T(n) = Θ(n)

Trường Hợp 2: Chi phí chia/kết hợp tương đương

Nếu f(n) = Θ(n^(log_b a))
T(n) = Θ(n^(log_b a) * log n)

Ví dụ minh họa:

// Merge Sort
T(n) = 2T(n/2) + n
// a = 2, b = 2, f(n) = n
// n^(log_2 2) = n
// n = Θ(n)
// → T(n) = Θ(n log n)

Trường Hợp 3: Chi phí chia/kết hợp lớn hơn

Nếu f(n) = Ω(n^(log_b a + ε)) với ε > 0
af(n/b) ≤ cf(n) với 0 < c < 1
T(n) = Θ(f(n))

Ví dụ minh họa:

// Matrix Multiplication (naive)
T(n) = 8T(n/2) + n^2
// a = 8, b = 2, f(n) = n^2
// n^(log_2 8) = n^3
// n^2 = O(n^(3+ε))
// → T(n) = Θ(n^3)

1.4. Cách Áp Dụng Step-by-Step

  1. Bước 1: Xác định các tham số
  • Tìm a (số bài toán con)
  • Tìm b (hệ số chia)
  • Xác định f(n) (chi phí chia/kết hợp)
  1. Bước 2: Tính n^(log_b a)
   // Ví dụ với Merge Sort:
   // a = 2, b = 2
   // n^(log_2 2) = n^1 = n
  1. Bước 3: So sánh f(n) với n^(log_b a)
  • Kiểm tra f(n) có nhỏ hơn, bằng, hay lớn hơn n^(log_b a)
  • Xác định trường hợp phù hợp
  1. Bước 4: Áp dụng công thức tương ứng
   // Ví dụ với Merge Sort:<br>   // f(n) = n = Θ(n^(log_2 2))<br>   // → Trường hợp 2<br>   // → T(n) = Θ(n log n)

2. Phân Tích Thuật Toán Đệ Quy Nâng Cao

2.1. Cơ Sở Của Phân Tích Đệ Quy

Khi phân tích một thuật toán đệ quy, chúng ta cần hiểu rằng thuật toán chia nhỏ bài toán thành các bài toán con và kết hợp kết quả lại. Quá trình này tạo ra một cây đệ quy với các đặc điểm quan trọng.

2.2. Các Thành Phần Của Phương Trình Đệ Quy

T(n) = aT(n/b) + f(n)
  1. Base Case (Trường hợp cơ sở):
// Thường là khi n đạt giá trị nhỏ nhất
T(1) = c  // c là hằng số
  1. Recursive Case (Trường hợp đệ quy):
// Công thức tổng quát cho các trường hợp khác
T(n) = aT(n/b) + f(n)

2.3. Ví Dụ Chi Tiết: QuickSort

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // pi là chỉ số phân vùng
        int pi = partition(arr, low, high);

        // Sắp xếp các phần tử trước và sau phân vùng
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// Phân tích:
// Trường hợp tốt nhất: T(n) = 2T(n/2) + O(n)
// Trường hợp xấu nhất: T(n) = T(n-1) + O(n)

2.4. Các Dạng Đệ Quy Phổ Biến

  1. Đệ Quy Tuyến Tính:
// Ví dụ: Tính giai thừa
int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n-1);
}
// T(n) = T(n-1) + O(1)
// → T(n) = O(n)
  1. Đệ Quy Chia Đôi:
// Ví dụ: Binary Search
int binarySearch(int arr[], int l, int r, int x) {
    if (r >= l) {
        int mid = l + (r - l) / 2;
        if (arr[mid] == x) return mid;
        if (arr[mid] > x) return binarySearch(arr, l, mid - 1, x);
        return binarySearch(arr, mid + 1, r, x);
    }
    return -1;
}
// T(n) = T(n/2) + O(1)
// → T(n) = O(log n)
  1. Đệ Quy Đa Phân Nhánh:
// Ví dụ: Strassen Matrix Multiplication
// T(n) = 7T(n/2) + O(n^2)
// → T(n) = O(n^log_2 7)

2.5. Phương Pháp Phân Tích Chi Tiết

2.5.1. Xác Định Base Case

Xác định base case là bước đầu tiên và quan trọng nhất trong phân tích đệ quy. Đây là điểm dừng của thuật toán và quyết định tính đúng đắn của toàn bộ quá trình.

// Ví dụ với tìm kiếm nhị phân
int binarySearch(int arr[], int left, int right, int x) {
    // Base case 1: Không tìm thấy phần tử
    if (left > right) {
        return -1;  // Chi phí O(1)
    }

    // Base case 2: Tìm thấy phần tử
    int mid = left + (right - left) / 2;
    if (arr[mid] == x) {
        return mid;  // Chi phí O(1)
    }

    // Recursive cases...
}

// Phân tích base case:
// T(1) = c1  // Trường hợp mảng có 1 phần tử
// T(0) = c2  // Trường hợp mảng rỗng
// Trong đó c1, c2 là các hằng số

2.5.2. Xây Dựng Công Thức Đệ Quy

Sau khi có base case, chúng ta cần xác định chính xác cách bài toán được chia nhỏ và chi phí liên quan.

// Ví dụ với Merge Sort
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        // Phân tích công thức đệ quy:

        // 1. Số lượng cuộc gọi đệ quy (a)
        mergeSort(arr, left, mid);      // 1 cuộc gọi
        mergeSort(arr, mid + 1, right); // 1 cuộc gọi
        // Tổng: a = 2 cuộc gọi

        // 2. Kích thước bài toán con (n/b)
        // Mỗi lần chia đôi kích thước: b = 2
        // Kích thước mỗi bài toán con = n/2

        // 3. Chi phí chia và kết hợp f(n)
        merge(arr, left, mid, right); // Chi phí O(n)

        // → Công thức: T(n) = 2T(n/2) + O(n)
    }
}

2.5.3. Kỹ Thuật Triển Khai

Sau khi có công thức đệ quy, chúng ta có thể triển khai theo nhiều cách khác nhau để tìm độ phức tạp.

// Ví dụ với Merge Sort: T(n) = 2T(n/2) + n

// Cách 1: Triển khai trực tiếp
T(n) = 2T(n/2) + n
     = 2[2T(n/4) + n/2] + n
     = 4T(n/4) + n + n
     = 4[2T(n/8) + n/4] + 2n
     = 8T(n/8) + n + n + n
     ...
     = nT(1) + n⋅log n
     = O(n log n)

// Cách 2: Vẽ cây đệ quy
/*
                    n
            n/2           n/2
        n/4    n/4    n/4    n/4
       ...     ...     ...     ...

    - Số tầng: log n
    - Chi phí mỗi tầng: n
    → Tổng chi phí: n⋅log n
*/

// Cách 3: Sử dụng Master Theorem
/*
a = 2, b = 2, f(n) = n
n^(log_b a) = n^(log_2 2) = n
f(n) = Θ(n^(log_b a))
→ Trường hợp 2: T(n) = Θ(n log n)
*/

2.5.4. Một Số Mẫu Phân Tích Thường Gặp

// 1. Phân tích tìm kiếm nhị phân
T(n) = T(n/2) + O(1)
// → O(log n)

// 2. Phân tích Quick Sort (trường hợp trung bình)
T(n) = 2T(n/2) + O(n)
// → O(n log n)

// 3. Phân tích tháp Hà Nội
T(n) = 2T(n-1) + 1
// → O(2^n)

// 4. Phân tích Strassen Matrix Multiplication
T(n) = 7T(n/2) + O(n^2)
// → O(n^log_2 7)
Khi thực hiện phân tích một thuật toán đệ quy, việc áp dụng có hệ thống các bước trên sẽ giúp chúng ta có cái nhìn toàn diện và chính xác về độ phức tạp của thuật toán.

3. Phân Tích Amortized – Chi Phí Khấu Hao

Đôi khi, một thao tác có thể tốn nhiều thời gian, nhưng nếu xét trung bình qua nhiều lần thì chi phí lại thấp hơn.

Ví dụ với Dynamic Array:

C++
class DynamicArray {
    int* arr;
    int size;    // Kích thước hiện tại
    int capacity;  // Sức chứa tối đa

public:
    void push_back(int x) {
        if(size == capacity) {
            // Cấp phát mảng mới gấp đôi
            capacity *= 2;
            int* new_arr = new int[capacity];
            // Copy dữ liệu sang
            for(int i = 0; i < size; i++)
                new_arr[i] = arr[i];
            delete[] arr;
            arr = new_arr;
        }
        arr[size++] = x;
    }
};

// Phân tích:
// - Thông thường: O(1)
// - Khi cần resize: O(n)
// Nhưng xét trung bình (amortized):
// - Sau n push_back, tổng chi phí = O(n)
// - Chi phí trung bình = O(1)

4. Các Kỹ Thuật Tối Ưu Độ Phức Tạp

4.1 Sử Dụng Cấu Trúc Dữ Liệu Phù Hợp

C++
// Tìm kiếm một phần tử
// Cách 1: Array - O(n)
bool find1(int x) {
    for(int i = 0; i < n; i++)
        if(arr[i] == x) return true;
    return false;
}

// Cách 2: Binary Search Tree - O(log n)
bool find2(Node* root, int x) {
    if(!root) return false;
    if(root->val == x) return true;
    if(x < root->val) 
        return find2(root->left, x);
    return find2(root->right, x);
}

// Cách 3: Hash Table - O(1) trung bình
bool find3(int x) {
    return hashTable.count(x) > 0;
}

4.2 Kỹ Thuật Hai Con Trỏ

C++
// Tìm cặp số có tổng = x
// Cách 1: Brute Force - O(n^2)
void findPair1(int arr[], int n, int x) {
    for(int i = 0; i < n; i++)
        for(int j = i+1; j < n; j++)
            if(arr[i] + arr[j] == x)
                cout << i << " " << j;
}

// Cách 2: Two Pointers - O(n)
// (Với mảng đã sắp xếp)
void findPair2(int arr[], int n, int x) {
    int l = 0, r = n-1;
    while(l < r) {
        if(arr[l] + arr[r] == x) {
            cout << l << " " << r;
            return;
        }
        if(arr[l] + arr[r] > x) r--;
        else l++;
    }
}

VI. Phân Tích Thuật Toán Qua Các Bài Toán Thực Tế

1. Case Study: Bài Toán Tìm Kiếm

Hãy cùng phân tích chi tiết các cách tiếp cận cho bài toán tìm kiếm, từ đơn giản đến phức tạp:

C++
// Bài toán: Tìm vị trí của x trong mảng n phần tử
// Input: arr[n], x 
// Output: vị trí của x, hoặc -1 nếu không tìm thấy

// === Cách 1: Linear Search - O(n) ===
int linearSearch(int arr[], int n, int x) {
    // Duyệt từng phần tử, so sánh với x
    for(int i = 0; i < n; i++) {
        if(arr[i] == x) return i;
    }
    return -1;
}
/* Phân tích:
1. Ưu điểm:
   - Đơn giản, dễ implement
   - Hoạt động với mảng chưa sắp xếp
   - Không cần thêm bộ nhớ

2. Nhược điểm:
   - Thời gian tìm kiếm tỷ lệ thuận với n
   - Không tận dụng được tính chất đã sắp xếp (nếu có)
*/

// === Cách 2: Binary Search - O(log n) ===
int binarySearch(int arr[], int n, int x) {
    int left = 0, right = n-1;

    while(left <= right) {
        // Tìm phần tử giữa
        int mid = (left + right)/2;

        if(arr[mid] == x) return mid;

        // Loại bỏ nửa mảng không chứa x
        if(arr[mid] < x)
            left = mid + 1;
        else 
            right = mid - 1;
    }
    return -1;
}
/* Phân tích:
1. Ưu điểm:
   - Thời gian tìm kiếm giảm đáng kể: log2(n)
   - Hiệu quả với dữ liệu lớn
   - Không cần thêm bộ nhớ

2. Nhược điểm:
   - Yêu cầu mảng đã sắp xếp
   - Code phức tạp hơn Linear Search
   - Không phù hợp với mảng nhỏ (overhead của việc chia đôi)
*/

// === Cách 3: Hash Table - O(1) average ===
class Solution {
    unordered_map<int, int> hash; // value -> index
public:
    void preprocess(int arr[], int n) {
        for(int i = 0; i < n; i++)
            hash[arr[i]] = i;
    }

    int find(int x) {
        if(hash.count(x)) 
            return hash[x];
        return -1;
    }
};
/* Phân tích:
1. Ưu điểm:
   - Tìm kiếm cực nhanh: O(1) trung bình
   - Không cần sắp xếp mảng
   - Có thể update/delete nhanh

2. Nhược điểm:
   - Tốn thêm O(n) bộ nhớ
   - Có thể bị collision (va chạm)
   - Chi phí preprocessing: O(n)
   - Trong worst case có thể lên tới O(n)
*/

2. Tối Ưu Hóa Thông Qua Quan Sát

Đôi khi chúng ta có thể tối ưu thuật toán bằng cách quan sát kỹ bài toán:

C++
// Bài toán: Tìm số xuất hiện nhiều nhất trong mảng
// Input: arr[n]
// Output: phần tử xuất hiện nhiều nhất

// === Cách 1: Brute Force - O(n^2) ===
int findMajority1(int arr[], int n) {
    for(int i = 0; i < n; i++) {
        // Đếm số lần xuất hiện của arr[i]
        int count = 0;
        for(int j = 0; j < n; j++)
            if(arr[j] == arr[i]) 
                count++;

        if(count > n/2) return arr[i];
    }
    return -1;
}

// === Cách 2: Sorting - O(n log n) ===
int findMajority2(int arr[], int n) {
    // Sort array first
    sort(arr, arr + n);

    // Phần tử giữa luôn là majority element
    // nếu nó xuất hiện > n/2 lần
    int candidate = arr[n/2];
    int count = 0;
    for(int i = 0; i < n; i++)
        if(arr[i] == candidate) 
            count++;

    return count > n/2 ? candidate : -1;
}

// === Cách 3: Moore's Voting Algorithm - O(n) ===
int findMajority3(int arr[], int n) {
    // Step 1: Tìm candidate
    int candidate = arr[0], count = 1;
    for(int i = 1; i < n; i++) {
        if(count == 0) {
            candidate = arr[i];
            count = 1;
        }
        else if(arr[i] == candidate)
            count++;
        else
            count--;
    }

    // Step 2: Verify candidate
    count = 0;
    for(int i = 0; i < n; i++)
        if(arr[i] == candidate)
            count++;

    return count > n/2 ? candidate : -1;
}
/* Phân tích Moore's Voting:
1. Ý tưởng: 
   - Nếu một phần tử xuất hiện > n/2 lần
   - Thì sau khi "loại bỏ" các cặp phần tử khác nhau
   - Phần tử còn lại chắc chắn là majority element

2. Ưu điểm:
   - O(n) time, O(1) space
   - Code đơn giản
   - Chỉ cần 2 pass qua mảng

3. Nhược điểm:
   - Khó hiểu ý tưởng 
   - Chỉ áp dụng được cho bài toán majority element
*/

3. Kết Hợp Các Kỹ Thuật

Nhiều khi để có được giải thuật tối ưu, chúng ta cần kết hợp nhiều kỹ thuật khác nhau:

C++
// Bài toán: Tìm số cặp số có tổng bằng k
// Input: arr[n], k
// Output: số cặp (i,j) sao cho arr[i] + arr[j] = k

// === Cách 1: Brute Force - O(n^2) ===
int countPairs1(int arr[], int n, int k) {
    int count = 0;
    for(int i = 0; i < n; i++)
        for(int j = i+1; j < n; j++)
            if(arr[i] + arr[j] == k)
                count++;
    return count;
}

// === Cách 2: Two Pointers + Sorting - O(n log n) === 
int countPairs2(int arr[], int n, int k) {
   // Sort array để có thể dùng 2 pointers
   sort(arr, arr + n);
   
   int count = 0;
   int left = 0, right = n-1;
   
   while(left < right) {
       int sum = arr[left] + arr[right];
       
       if(sum == k) {
           // Tìm được 1 cặp số
           count++;
           
           // Skip các phần tử trùng nhau
           int x = arr[left], y = arr[right];
           while(left < right && arr[left] == x) left++;
           while(left < right && arr[right] == y) right--;
       }
       else if(sum < k) {
           left++;
       }
       else {
           right--;
       }
   }
   return count;
}

// === Cách 3: Hash Map - O(n) ===
int countPairs3(int arr[], int n, int k) {
   unordered_map<int, int> freq;
   int count = 0;
   
   // Duyệt mảng một lần
   for(int i = 0; i < n; i++) {
       // Tìm số phần tử complement đã xuất hiện trước đó  
       int complement = k - arr[i];
       if(freq.count(complement)) {
           count += freq[complement];
       }
       // Tăng tần suất của arr[i]
       freq[arr[i]]++;
   }
   
   return count;
}

/* So sánh 3 cách tiếp cận:

1. Brute Force - O(n^2):
  - Ưu điểm: Code đơn giản, không cần bộ nhớ phụ
  - Nhược điểm: Chậm với n lớn

2. Two Pointers - O(n log n):
  - Ưu điểm: 
    + Nhanh hơn brute force
    + Không tốn bộ nhớ phụ
  - Nhược điểm:
    + Cần sort mảng (thay đổi mảng gốc)
    + Code phức tạp hơn
    + Không tối ưu nhất về thời gian

3. Hash Map - O(n):
  - Ưu điểm:
    + Tốc độ nhanh nhất 
    + Không cần thay đổi mảng gốc
    + Code khá đơn giản
  - Nhược điểm:
    + Tốn O(n) bộ nhớ phụ
    + Có thể gặp vấn đề với collision

Lựa chọn phương pháp phù hợp:
- n nhỏ (<100): Brute force đủ tốt
- n vừa (100-10^4): Two pointers là lựa chọn cân bằng
- n lớn (>10^4): Hash map là lựa chọn tối ưu
*/

// === Mở rộng: Tìm 3 số có tổng bằng k ===
int countTriplets(int arr[], int n, int k) {
   // Sort array trước
   sort(arr, arr + n);
   
   int count = 0;
   
   // Fix phần tử đầu tiên
   for(int i = 0; i < n-2; i++) {
       // Tìm cặp số có tổng = k - arr[i] trong đoạn còn lại
       int target = k - arr[i];
       int left = i+1, right = n-1;
       
       while(left < right) {
           int sum = arr[left] + arr[right];
           if(sum == target) {
               count++;
               left++;
               right--; 
           }
           else if(sum < target) {
               left++;
           }
           else {
               right--;
           }
       }
   }
   
   return count;
}

4. Tối Ưu Với Cấu Trúc Dữ Liệu Đặc Biệt

Một số bài toán yêu cầu thiết kế cấu trúc dữ liệu đặc biệt để đạt hiệu năng tối ưu:

C++
// === Bài toán: Design an LRU Cache ===
class LRUCache {
private:
    int capacity;

    // Double linked list để lưu thứ tự truy cập
    struct Node {
        int key, value;
        Node *prev, *next;
        Node(int k, int v): key(k), value(v), prev(NULL), next(NULL) {}
    };

    Node *head, *tail;

    // Hash map để O(1) access
    unordered_map<int, Node*> cache;

    void addToFront(Node* node) {
        node->next = head->next;
        node->prev = head;
        head->next->prev = node;
        head->next = node;
    }

    void removeNode(Node* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

public:
    LRUCache(int cap) {
        capacity = cap;
        head = new Node(0,0);
        tail = new Node(0,0);
        head->next = tail;
        tail->prev = head;
    }

    int get(int key) {
        if(cache.count(key)) {
            Node* node = cache[key];
            removeNode(node);
            addToFront(node);
            return node->value;
        }
        return -1;
    }

    void put(int key, int value) {
        if(cache.count(key)) {
            Node* node = cache[key];
            node->value = value;
            removeNode(node);
            addToFront(node);
        }
        else {
            Node* node = new Node(key, value);
            cache[key] = node;
            addToFront(node);

            if(cache.size() > capacity) {
                Node* lru = tail->prev;
                removeNode(lru);
                cache.erase(lru->key);
                delete lru;
            }
        }
    }
};

/* Phân tích LRU Cache:
1. Yêu cầu:
   - get(key): Trả về giá trị của key, -1 nếu không tồn tại
   - put(key,value): Thêm/cập nhật cặp key-value
   - capacity: Khi đầy, xóa phần tử least recently used

2. Thiết kế:
   - Double linked list: Lưu thứ tự truy cập
   - Hash map: Truy cập nhanh node

3. Độ phức tạp:
   - get(): O(1)
   - put(): O(1) 
   - Space: O(capacity)

4. Ưu điểm:
   - Thao tác nhanh O(1)
   - Dễ maintain least recently used

5. Nhược điểm:
   - Tốn bộ nhớ
   - Code phức tạp
*/

VII. Phân Tích Thuật Toán Nâng Cao & Kỹ Thuật Tối Ưu Hóa

1. Lập Trình Động – Đánh Đổi Giữa Không Gian và Thời Gian

Hãy cùng khám phá cách tối ưu hóa cả độ phức tạp thời gian và không gian bằng lập trình động, cùng với các đánh đổi liên quan:

C++
// Bài toán: Tính số Fibonacci thứ n

// === Cách 1: Đệ quy đơn giản - Thời gian: O(2^n), Không gian: O(n) ===
int fib1(int n) {
    if (n <= 1) return n;
    return fib1(n - 1) + fib1(n - 2);
}
/* Phân tích:
- Độ phức tạp thời gian xây dựng cây nhị phân chiều cao n.
- Mỗi cấp nhân đôi số lời gọi.
- Kết quả là T(n) = T(n-1) + T(n-2) = O(2^n).
- Độ phức tạp không gian O(n) do ngăn xếp đệ quy.
*/

// === Cách 2: Lập trình động với ghi nhớ - Thời gian: O(n), Không gian: O(n) ===
int fib2(int n, vector<int>& memo) {
    if (n <= 1) return n; // Trường hợp cơ bản.

    if (memo[n] != -1) return memo[n]; // Kiểm tra đã tính trước chưa.

    memo[n] = fib2(n - 1, memo) + fib2(n - 2, memo); // Tính toán và lưu kết quả.
    return memo[n];
}
/* Phân tích:
- Mỗi bài toán con được giải đúng 1 lần và lưu lại.
- Giảm độ phức tạp thời gian xuống O(n).
- Nhưng sử dụng thêm O(n) bộ nhớ cho mảng ghi nhớ.
*/

// === Cách 3: Lập trình động lặp - Thời gian: O(n), Không gian: O(1) ===
int fib3(int n) {
    if (n <= 1) return n;

    int prev2 = 0, prev1 = 1; // Chỉ cần giữ hai giá trị cuối.

    for (int i = 2; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}
/* Phân tích:
- Cùng độ phức tạp thời gian O(n) như cách ghi nhớ.
- Không gian giảm xuống O(1) nhờ chỉ lưu trữ các giá trị cần thiết.
- Thể hiện rõ mô hình đánh đổi giữa không gian và thời gian.
*/

2. Phân Tích Amortized Chi Tiết

Hãy phân tích ví dụ phức tạp về phân tích chi phí bình quân:

C++
// Triển khai Vector (mảng động)
template<typename T>
class Vector {
    T* arr;
    int size;     // Số phần tử hiện tại
    int capacity; // Tổng không gian đã cấp phát
    
    void grow() { // Mở rộng mảng
        T* newArr = new T[capacity * 2];
        for(int i = 0; i < size; i++) {
            newArr[i] = arr[i];
        }
        delete[] arr;
        arr = newArr;
        capacity *= 2;
    }
    
public:
    Vector(): size(0), capacity(1) {
        arr = new T[1];
    }
    
    void push_back(T val) {
        if(size == capacity) {
            grow();
        }
        arr[size++] = val;
    }
};

/* Phân tích chi phí bình quân:

1. Mô hình chi phí:
   - Thêm phần tử thông thường: 1 đơn vị
   - Khi mở rộng mảng: n đơn vị sao chép

2. Mô hình tăng trưởng:
   - Dãy dung lượng: 1, 2, 4, 8, 16, ...
   - Mở rộng tại các bước: 1, 2, 4, 8, ...

3. Phân tích chi phí cho n thao tác:
   - Thêm thông thường: n thao tác × 1 đơn vị = n đơn vị
   - Chi phí mở rộng: 1 + 2 + 4 + 8 + ... ≈ 2n đơn vị
   - Tổng chi phí ≈ 3n đơn vị

4. Vì vậy:
   - Chi phí bình quân mỗi thao tác = Tổng chi phí / n
   - = 3n/n = O(1)
*/

3. Phân Tích Thuật Toán Với Nhiều Tham Số

Thực tế, các vấn đề thường có nhiều tham số đầu vào ảnh hưởng đến độ phức tạp:

C++
// Bài toán: Tìm tất cả cặp điểm cách nhau không quá d

// === Cách Brute Force - O(n²) ===
vector<pair<Point, Point>> findClosePairs1(vector<Point>& points, double d) {
    vector<pair<Point, Point>> result;
    int n = points.size();
    
    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < n; j++) {
            if(distance(points[i], points[j]) <= d) {
                result.push_back({points[i], points[j]});
            }
        }
    }
    return result;
}

// === Cách Dùng Grid ===
class PointFinder {
    double gridSize;
    map<pair<int, int>, vector<Point>> grid;
    
    pair<int, int> getCell(Point p) {
        return {floor(p.x / gridSize), floor(p.y / gridSize)};
    }
    
    vector<pair<int, int>> getNeighborCells(pair<int, int> cell) {
        vector<pair<int, int>> neighbors;
        for(int dx = -1; dx <= 1; dx++) {
            for(int dy = -1; dy <= 1; dy++) {
                neighbors.push_back({cell.first + dx, cell.second + dy});
            }
        }
        return neighbors;
    }
    
public:
    PointFinder(double d): gridSize(d) {}
    
    void addPoint(Point p) {
        grid[getCell(p)].push_back(p);
    }
    
    vector<Point> findClosePoints(Point p) {
        vector<Point> result;
        auto cell = getCell(p);
        
        for(auto& neighCell : getNeighborCells(cell)) {
            for(auto& candPoint : grid[neighCell]) {
                if(distance(p, candPoint) <= gridSize) {
                    result.push_back(candPoint);
                }
            }
        }
        return result;
    }
};

/* Phân tích phức tạp:
n = số điểm
d = ngưỡng khoảng cách
s = kích thước không gian

1. Brute Force:
   - Thời gian: O(n²)
   - Không gian: O(1) trừ output

2. Grid:
   - Thời gian:
     * Trung bình: O(n) nếu phân phối điểm đều
     * Xấu nhất: O(n²) nếu tất cả điểm nằm cùng hoặc sát ô lưới
   - Không gian: O(n) cho cấu trúc lưới
   - Tiền xử lý: O(n) để xây dựng lưới
*/

4. Phân Tích Thuật Toán Ngẫu Nhiên

Hãy xem xét cách sử dụng ngẫu nhiên hóa để cải thiện thời gian chạy kỳ vọng:

C++
// Bài toán: Tìm phần tử nhỏ nhất thứ k

// === Thuật toán QuickSelect ===
int quickSelect(vector<int>& arr, int k) {
    int n = arr.size();
    int pivotIdx = rand() % n;
    int pivot = arr[pivotIdx];
    
    vector<int> left, right;
    for(int i = 0; i < n; i++) {
        if(i == pivotIdx) continue;
        
        if(arr[i] <= pivot) 
            left.push_back(arr[i]);
        else 
            right.push_back(arr[i]);
    }
    
    if(k <= left.size())
        return quickSelect(left, k);
    else if(k == left.size() + 1)
        return pivot;
    else
        return quickSelect(right, k - left.size() - 1);
}

/* Phân tích ngẫu nhiên:

1. Trường hợp xấu nhất: O(n²)
   - Các lựa chọn pivot xấu liên tiếp
   - Tương tự QuickSort trường hợp xấu nhất

2. Trường hợp trung bình: O(n)
   - Pivot ngẫu nhiên chia tốt với xác suất cao
   - Mỗi lời gọi đệ quy giảm kích thước bài toán đáng kể
   
3. Phân tích xác suất:
   - P(chia tốt) ≥ 1/4 mỗi lần
   - Độ sâu đệ quy kỳ vọng = O(log n)
   - Công việc mỗi cấp = O(n)
   - E[total work] = O(n)

4. Tại sao ngẫu nhiên hóa hiệu quả:
   - Tránh trường hợp xấu nhất
   - Không phụ thuộc đầu vào
   - Đảm bảo hiệu suất trung bình tốt
*/

VIII. Tổng Kết

1. Tóm Tắt Các Bước Phân Tích

  1. Xác định input size n
  2. Đếm các phép toán cơ bản
  3. Tính toán độ phức tạp
  4. Xem xét các case đặc biệt
  5. Tối ưu nếu cần thiết

2. Best Practices

  • Luôn xét worst case trước
  • Cân nhắc tradeoff giữa time/space
  • Chọn cấu trúc dữ liệu phù hợp
  • Tối ưu sớm khi cần thiết

3. Lời Khuyên Từ Cá Nhân

  • Làm nhiều bài tập thực hành
  • Tập trung vào worst case analysis
  • Thử nghiệm với nhiều size input
  • Đo đạc benchmark thực tế

4. Resources

  • Sách: Introduction to Algorithms (CLRS)
  • Online: GeeksforGeeks, LeetCode
  • Khóa học: Coursera Algorithms
  • Blog: learningaiwithlosers.com

Bài viết được viết bởi Loser1 từ Learning AI with Losers. Follow chúng tôi tại:

[Hết]

quyminhhuy0@gmail.com
quyminhhuy0@gmail.com
Articles: 39

Newsletter Updates

Enter your email address below and subscribe to our newsletter

Subscribe
Notify of
guest

1 Comment
Inline Feedbacks
View all comments

[…] Phần 1: Nền Tảng Cơ Bản 📖 Phần 2: Kỹ Thuật Nâng Cao Table Of […]

AI Assistant
Hi! How can I help you today?
Stou doloremque quo odio repudiandae sunt eveniet,. Heavy equipment transport monroe ny logi transports fast & reliable heavy equipment transport & transport services.