Physical Address

304 North Cardinal St.
Dorchester Center, MA 02124

thumdnailday1_lythuyet1

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 P1)

Article by Loser1 – Learning AI with Losers

Table Of Contents
  1. Lời Mở Đầu
  2. Phân Tích Thuật Toán – Từ ZERO TO HERO
  3. II. Phân Tích Độ Phức Tạp Thời Gian
  4. III. Phân Tích Độ Phức Tạp Của Các Cấu Trúc Phổ Biến

Lời Mở Đầu

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?

  • Các bạn mới bắt đầu học lập trình, muốn xây dựng nền tảng vững chắc.
  • Những lập trình viên muốn nâng cao kỹ năng tối ưu hóa thuật toán và hiệu suất phần mềm.
  • Các bạn chuẩn bị cho các kỳ phỏng vấn hoặc ôn thi Học phần DSA.

Bạn sẽ học được gì?

  • Những khái niệm quan trọng nhất về DSA.
  • Các kỹ thuật từ cơ bản đến nâng cao trong tối ưu hóa thuật toán.
  • Cách áp dụng kiến thức vào thực tế để xử lý các bài toán hiệu quả.

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.


Phần 1: Nền Tảng và Độ Phức Tạp Thuật Toán

1. Giới Thiệu Về DSA Và Tầm Quan Trọng

Khái niệm cơ bản:

  • DSA (Data Structures and Algorithms) là nền tảng quan trọng trong khoa học máy tính.
  • Cần thiết cho việc phát triển phần mềm hiệu quả và tối ưu.

Tầm quan trọng:

  • Tối ưu hóa hiệu suất:
    • Giảm thời gian xử lý.
    • Tiết kiệm tài nguyên hệ thống.
  • Giải quyết vấn đề:
    • Cung cấp các phương pháp tiếp cận có cấu trúc.
    • Giúp xử lý dữ liệu hiệu quả.
  • Phát triển kỹ năng:
    • Tư duy logic.
    • Khả năng giải quyết vấn đề.
    • Kỹ năng lập trình.

Phân Tích Thuật Toán – Từ ZERO TO HERO


1. Tại Sao Phải Phân Tích Thuật Toán?

Hãy xem một ví dụ cụ thể để hiểu rõ hơn:

Python
# 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:

  • Cách 1: với n = 1 triệu phần tử → mất ~1,000,000,000,000 phép so sánh.
  • Cách 2: với n = 1 triệu phần tử → chỉ mất ~1,000,000 phép so sánh.

→ Đây chính là lý do chúng ta cần phân tích thuật toán!

2. Ba Tiêu Chí Đánh Giá Một Thuật Toán

  1. Tính Đúng Đắn (Correctness)
    • Thuật toán phải cho kết quả chính xác với mọi input hợp lệ.
    • Ví dụ: Thuật toán sắp xếp phải đảm bảo dãy output được sắp xếp đúng thứ tự.
  2. Không Gian Bộ Nhớ (Space Complexity)
    • Lượng bộ nhớ thuật toán sử dụng, bao gồm:
      • Bộ nhớ tĩnh: biến, mảng khai báo sẵn.
      • Bộ nhớ động: stack trong đệ quy, heap allocation.
  3. Thời Gian Thực Hiện (Time Complexity)
    • Số lượng phép toán cơ bản thuật toán thực hiện, thường là tiêu chí quan trọng nhất.

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):


II. Phân Tích Độ Phức Tạp Thời Gian

1. Khái Niệm Hàm Thời Gian T(n)

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:

  • Khi kích thước dữ liệu đầu vào (n) thay đổi, thuật toán sẽ mất bao lâu để xử lý hết tất cả.
  • Các thuật toán có độ phức tạp thời gian khác nhau, ví dụ như O(1) (hằng số), O(n) (tuyến tính), O(n^2) (bình phương), O(log n) (logarit), v.v.

Ví dụ cụ thể:

  1. Hàm thời gian T(n) = C1 (hằng số):
C++
int getFirst(int arr[], int n) {
    return arr[0];  // Trả về phần tử đầu tiên
}
  • Đoạn code trên có thời gian chạy cố định, bất kể mảng có bao nhiêu phần tử. Việc truy cập phần tử đầu tiên luôn mất thời gian cố định (1 bước). Do đó, T(n) = C1, tức là O(1) – Độ phức tạp hằng số.
  1. Hàm thời gian T(n) = C2 * n + C3:
C++
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;
}
  • Đoạn code này có một vòng lặp duyệt qua tất cả các phần tử trong mảng để tính tổng.
  • Việc cộng dồn cho mỗi phần tử mất O(1) bước, và vì có n phần tử nên số bước thực hiện sẽ là n. Tổng thời gian chạy là C2 * n + C3, tương ứng với T(n) = O(n) (Độ phức tạp tuyến tính).
  1. Hàm thời gian T(n) = C4 * n^2 + C5 * n + C6:
C++
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;
        }
    }
}
  • Trong ví dụ trên, có hai vòng lặp lồng nhau, mỗi vòng lặp chạy n lần.
  • Vì vậy, số bước thực hiện là n * n = n^2, và độ phức tạp thời gian là T(n) = O(n^2) (Độ phức tạp bình phương).

2. Các Quy Tắc Tính T(n)

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:

2.1 Quy Tắc Cộng

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))).

C++
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)
  • Giải thích:
    • Trong ví dụ này, có hai khối mã độc lập: Block 1 có độ phức tạp O(n) và Block 2 có độ phức tạp O(n^2).
    • Khi tính toán tổng thời gian chạy của thuật toán, chúng ta cộng các độ phức tạp của từng khối. Tuy nhiên, khi so sánh O(n)O(n^2), ta chỉ cần chọn độ phức tạp lớn nhất. Do đó, thời gian chạy của thuật toán sẽ là O(n^2).
  • Quy tắc cộng trong thực tế:
    Nếu thuật toán có nhiều khối mã thực hiện lần lượt (không lồng nhau), độ phức tạp thời gian sẽ là tổng của độ phức tạp của các khối mã. Chọn độ phức tạp lớn nhất để đơn giản hóa.

2.2 Quy Tắc Nhân

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).

C++
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)
  • Giải thích:
    • Ở đây, vòng lặp ngoài chạy n lần, và trong mỗi lần chạy của vòng lặp ngoài, vòng lặp trong cũng chạy n lần.
    • Do đó, tổng số bước thực hiện là n * n = n^2, và độ phức tạp của thuật toán là O(n^2).
  • Quy tắc nhân trong thực tế:
    Khi có vòng lặp lồng nhau, ta nhân độ phức tạp của từng vòng lặp. Đối với trường hợp như trên, độ phức tạp là O(n) * O(n) = O(n^2).

2.3. Lưu Ý Khi Phân Tích Big O

  1. Bỏ qua hằng số:
    Ví dụ: T(n) = 3n + 5 → O(n), không ghi O(3n) hay O(5).
  2. Chọn số mũ lớn nhất:
    Ví dụ: T(n) = 2n² + 10n + 100 → O(n²).
  3. Tập trung vào phần “chi phối”:
    Khi 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ư ).

Tổng Kết
  • T(n) là hàm thể hiện thời gian chạy của thuật toán: Là hàm phụ thuộc vào kích thước dữ liệu đầu vào (n).
  • Quy tắc cộng: Sử dụng khi các khối mã thực hiện độc lập nhau, độ phức tạp là tổng các độ phức tạp của từng khối mã.
  • Quy tắc nhân: Sử dụng khi các khối mã lồng nhau, độ phức tạp là tích của độ phức tạp của từng vòng lặp.

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!

3. Độ Phức Tạp Big-O

3.1 Định Nghĩa Toán Học

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.

3.2 Cách Hiểu Đơn Giản

  • O(f(n)) là một cách ước lượng “trần” của T(n).
  • Bỏ qua các hệ số và số hạng bậc thấp.
  • Chỉ quan tâm đến xu hướng tăng của hàm.

Ví dụ:

C++
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)

4. Các Loại Độ Phức Tạp Phổ Biến


4.1. Độ Phức Tạp O(1) – Độ Phức Tạp Hằng Số

Giải thích:

Độ 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.

Code ví dụ:
C++
int getFirstElement(int arr[]) {
    return arr[0]; // Lấy phần tử đầu tiên trong mảng
}
Giải thích:
  • Dù mảng có bao nhiêu phần tử, việc truy cập phần tử đầu tiên luôn diễn ra trong thời gian hằng số. Do đó, độ phức tạp là O(1).

4.2. Độ Phức Tạp O(n) – Độ Phức Tạp Tuyến Tính

Giải thích:

Độ 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.

Code ví dụ:

C++
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;
}
Giải thích:
  • Trong ví dụ này, ta phải duyệt qua tất cả các phần tử của mảng, tức là mất O(n) thời gian, với n là số phần tử trong mảng.

4.3. Độ Phức Tạp O(n^2) – Độ Phức Tạp Bình Phương

Giải thích:

Độ 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.

Code ví dụ:
C++
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ự
            }
        }
    }
}
Giải thích:
  • Thuật toán sắp xếp nổi bọt (Bubble Sort) thực hiện 2 vòng lặp lồng nhau, với mỗi vòng lặp đi qua tất cả các phần tử chưa được sắp xếp, dẫn đến độ phức tạp O(n^2).

4.4. Độ Phức Tạp O(log n) – Độ Phức Tạp Logarit

Giải thích:

Độ 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.

Code ví dụ:
C++
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
}
Giải thích:
  • Mỗi lần so sánh, thuật toán loại bỏ một nửa mảng, vì vậy số bước cần thiết giảm đi một nửa mỗi lần, dẫn đến độ phức tạp O(log n).

4.5. Độ Phức Tạp O(n log n) – Độ Phức Tạp Logarit Tuyến Tính

Giải thích:

Độ 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).

Code ví dụ (Merge Sort):
C++
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
    }
}
Giải thích:
  • Thuật toán Merge Sort chia mảng thành hai nửa và thực hiện sắp xếp đệ quy trên mỗi nửa. Việc chia đôi mảng mất O(log n) bước, trong khi việc hợp nhất (merge) hai mảng con mất O(n) thời gian. Kết quả là độ phức tạp tổng thể là O(n log n).

4.6. Độ Phức Tạp O(2^n) – Độ Phức Tạp Exponential

Giải thích:

Độ 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.

Code ví dụ:
C++
int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n-1) + fibonacci(n-2); // Tính dãy Fibonacci
}
Giải thích:
  • Thuật toán tính số Fibonacci theo cách đệ quy này sẽ tính lại rất nhiều giá trị nhiều lần, dẫn đến độ phức tạp O(2^n) vì số cuộc gọi đệ quy tăng theo cấp số nhân.

Tóm tắt:

  • O(1): Thực hiện cố định, không phụ thuộc vào kích thước dữ liệu.
  • O(n): Thực hiện một lần với mỗi phần tử trong dữ liệu.
  • O(n^2): Thực hiện mỗi phần tử kết hợp với mỗi phần tử khác (ví dụ sắp xếp nổi bọt).
  • O(log n): Độ phức tạp giảm dần một nửa dữ liệu mỗi lần (ví dụ tìm kiếm nhị phân).
  • O(n log n): Thường xuất hiện trong các thuật toán sắp xếp như Merge Sort.
  • O(2^n): Độ phức tạp tăng nhanh chóng theo số lượng phần tử (ví dụ Fibonacci đệ quy).

So sánh độ phức tạp:

Độ phức tạpn=10n=100n=1000
O(1)111
O(log n)3.326.649.97
O(n)101001000
O(n log n)33.26649970
O(n²)100100001000000
O(2ⁿ)10242¹⁰⁰2¹⁰⁰⁰

III. Phân Tích Độ Phức Tạp Của Các Cấu Trúc Phổ Biến

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:


1. Các Câu Lệnh Cơ Bản

  • Đặc điểm: Các câu lệnh đơn lẻ, không phụ thuộc vào n.
  • Ví dụ:
C++
  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ị
  • Giải thích:
    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.
    → Độ phức tạp luôn là O(1).

2. Cấu Trúc Rẽ Nhánh

2.1 If-Else

  • Quy tắc: Độ phức tạp bằng độ phức tạp của nhánh lớn nhất.
  • Công thức:
    T(n) = max(T_then(n), T_else(n))
    (Bỏ qua thời gian kiểm tra điều kiện vì nó là O(1)).
  • Ví dụ:
C++
  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];
          }
      }
  }
  • Phân tích:
    • Nhánh 1 có độ phức tạp O(n).
    • Nhánh 2 có độ phức tạp O(n²).
    • Tổng: T(n) = max(O(n), O(n²)) = O(n²).

2.2 Switch-Case

  • Quy tắc: Tương tự if-else. Độ phức tạp bằng case phức tạp nhất.
  • Ví dụ:
C++
  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;
              }
          }
  }
  • Phân tích:
    • Case 1: O(n).
    • Case 2: O(1).
    • Default: O(n²).
    • Tổng: T(n) = max(O(n), O(1), O(n²)) = O(n²).

3. Cấu Trúc Lặp

3.1 Vòng Lặp Đơn

  • Công thức: T(n) = Số lần lặp * Độ phức tạp thân vòng lặp.
  • Ví dụ 1:
C++
  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).

  • Ví dụ 2:
C++
  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²).

3.2 Vòng Lặp Với Bước Nhảy

  • Bước nhảy cộng (Ví dụ: i += c):
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ố).

  • Bước nhảy nhân (Ví dụ: i *= 2):
C++
  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).

3.3 Vòng Lặp Lồng Nhau

  • Ví dụ 1: Hai vòng lặp độc lập
C++
  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).

  • Ví dụ 2: Vòng lặp phụ thuộc
C++
  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)
      }
  }
  • Phân tích:
    • Khi i = 0: j chạy từ 0 đến n-1 → n lần.
    • Khi i = 1: j chạy từ 1 đến n-1 → n-1 lần.
    • Tổng số lần lặp: n + (n-1) + (n-2) + ... + 1 = n(n+1)/2.
      T(n) = O(n²).


4. Cấu Trúc Đệ Quy

4.1 Đệ Quy Tuyến Tính

Đệ 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).

Ví Dụ: Tính Giai Thừa

Để 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:

C++
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
}
  • Giải thích hàm:
    • Hàm factorial tính giai thừa của một số n.
    • Nếu n nhỏ hơn hoặc bằng 1, hàm sẽ trả về 1 (điều kiện dừng).
    • Nếu n lớn hơn 1, hàm sẽ gọi lại chính nó với giá trị n-1 (gọi đệ quy).
Cách Xây Dựng Công Thức Đệ Quy

Bây giờ, chúng ta sẽ phân tích thời gian chạy của hàm đệ quy này.

  1. Công thức đệ quy:
    • Mỗi lần gọi hàm factorial(n) sẽ gọi đệ quy một lần nữa với factorial(n-1).
    • Điều này có nghĩa là chúng ta gọi hàm này n lần (mỗi lần giảm giá trị n đi 1).
    • Mỗi lần gọi sẽ thực hiện một phép toán đơn giản, như phép nhân O(1).
    Vậy công thức đệ quy cho thời gian chạy sẽ là: T(n)=T(n−1)+O(1)
    • T(n-1) là thời gian chạy của hàm gọi đệ quy với giá trị n-1.
    • O(1) là thời gian thực hiện phép nhân.
  2. Giải quyết công thức đệ quy:
    • Bây giờ, chúng ta giải quyết công thức đệ quy bằng cách vẽ cây đệ quy.
    • Ở mỗi cấp độ của đệ quy, chúng ta thực hiện một phép toán O(1). Tổng số cấp độ là n.
    • Do đó, tổng thời gian chạy sẽ là tổng của O(1) thực hiện n lần, tức là O(n).
    Cuối cùng, độ phức tạp thời gian của hàm tính giai thừa là O(n).

Tóm Tắt

  • Mỗi lần gọi đệ quy giảm n đi 1.
  • Tổng số lần gọi đệ quy là n.
  • Độ phức tạp thời gian tổng thể là O(n).

4.2 Đệ Quy Chia Để Trị

Đệ 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.

Ví Dụ: Merge Sort

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à:

  1. Chia danh sách thành hai phần.
  2. Đệ quy sắp xếp từng phần.
  3. Kết hợp các phần đã sắp xếp lại với nhau.

Đây là mã nguồn của thuật toán Merge Sort:

C++
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)
}
  • Giải thích:
    • Nếu chỉ có một phần tử (l = r), thuật toán dừng lại.
    • Nếu có nhiều hơn một phần tử, thuật toán chia danh sách thành hai phần và gọi đệ quy cho mỗi phần.
    • Sau đó, hàm merge kết hợp hai phần đã sắp xếp lại thành một danh sách hoàn chỉnh.
Cách Xây Dựng Công Thức Đệ Quy
  1. Công thức đệ quy:
    • Mỗi lần gọi hàm mergeSort chia mảng thành hai phần và gọi đệ quy cho từng phần.
    • Do đó, mỗi lần gọi hàm sẽ thực hiện hai cuộc gọi đệ quy với mảng có kích thước là n/2.
    • Việc kết hợp các mảng lại với nhau (hàm merge) sẽ mất O(n) thời gian.
    Công thức đệ quy cho thời gian chạy của Merge Sort sẽ là: T(n)=2T(n/2)+O(n)
    • 2T(n/2) là thời gian chạy cho hai phần của mảng.
    • O(n) là thời gian cần để kết hợp các phần mảng lại với nhau.
  2. Giải quyết công thức đệ quy bằng Định lý Thợ (Master Theorem, xíu sẽ học ở dưới sau):
    • Công thức đệ quy có dạng T(n) = aT(n/b) + O(n^k), với a = 2, b = 2, và k = 1.
    • Định lý thợ giúp chúng ta tìm độ phức tạp thời gian của các thuật toán chia để trị.
    Theo định lý thợ, khi a = b^k, độ phức tạp thời gian là O(n log n). Do đó, độ phức tạp của Merge SortO(n log n).
Tóm Tắt
  • Thuật toán chia mảng thành hai phần, gọi đệ quy cho mỗi phần.
  • Thời gian tổng cộng cho mỗi bước là O(n) (do bước kết hợp các phần mảng).
  • Sử dụng Định lý Thợ để giải công thức đệ quy, chúng ta có độ phức tạp là O(n log n).

Tổng Kết
  1. Đệ Quy Tuyến Tính: Mỗi lần gọi đệ quy giảm n đi 1. Công thức đệ quy sẽ là T(n) = T(n-1) + O(1) và độ phức tạp là O(n).
  2. Đệ Quy Chia Để Trị: Mỗi lần gọi đệ quy chia vấn đề thành hai phần. Công thức đệ quy sẽ là T(n) = 2T(n/2) + O(n) và độ phức tạp là O(n log n), giải bằng Định lý Thợ.

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

1. Các Thuật Toán Sắp Xếp (Sorting)

// 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
*/

2. Các Thuật Toán Tìm Kiếm (Searching)

/*
+------------------+---------------+---------------+------------------+
| 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)            |
+------------------+---------------+---------------+------------------+
*/

3. Cây Nhị Phân Tìm Kiếm (BST)

/*
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!
*/

4. Heap

/*
+------------------+---------------+
| 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)     |
+------------------+---------------+
*/

5. String Matching

/*
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)
*/

6. Hash Table

/*
+------------------+---------------+---------------+------------------+
| 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
*/

7. Graph Algorithms

/*
+------------------+--------------------+------------------+
| 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)             |
+------------------+--------------------+------------------+
*/

8. Tips Phân Tích Độ Phức Tạp

  1. Quy tắc cơ bản:
   - 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
  1. Cách tối ưu:
   - 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)
  1. Mẹo thực tế:
   - 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

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:

[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

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

Newsletter Updates

Enter your email address below and subscribe to our newsletter

Subscribe
Notify of
guest

3 Comments
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 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 […]

AI Assistant
Hi! How can I help you today?
Adidas fleece hoodie. Heavy equipment transport franklin oh.