Phân Tích Hiệu Năng Giải Thuật: Time & Space Complexity

Chào mừng bạn đến với bài viết thứ hai trong series về cấu trúc dữ liệu và giải thuật. Ở bài viết trước, chúng ta đã làm quen với các khái niệm cơ bản. Hôm nay, chúng ta sẽ tìm hiểu sâu hơn về phân tích hiệu năng giải thuật.

Phân tích hiệu năng là một bước quan trọng trong việc thiết kế và lựa chọn giải thuật. Nó giúp chúng ta đánh giá khả năng của giải thuật khi xử lý dữ liệu lớn. Chúng ta sẽ tập trung vào hai khía cạnh chính: độ phức tạp thời gian và độ phức tạp không gian.

Độ Phức Tạp Thời Gian (Time Complexity)

Độ phức tạp thời gian mô tả thời gian thực thi của một giải thuật. Nó được biểu diễn như một hàm của kích thước đầu vào (n). Thay vì đo thời gian thực tế (giây, mili giây), chúng ta quan tâm đến số lượng các phép toán cơ bản mà giải thuật thực hiện.

Ví dụ, một giải thuật có thể thực hiện n phép gán, 2n phép so sánh và n/2 phép cộng. Tổng số phép toán sẽ là một hàm của n, cho phép ta so sánh hiệu quả của các giải thuật khác nhau một cách tổng quát.

Độ Phức Tạp Không Gian (Space Complexity)

Độ phức tạp không gian mô tả lượng bộ nhớ mà một giải thuật sử dụng. Tương tự như độ phức tạp thời gian, nó cũng được biểu diễn như một hàm của kích thước đầu vào (n). Bộ nhớ này bao gồm bộ nhớ cho dữ liệu đầu vào, các biến trung gian và cấu trúc dữ liệu bổ sung.

Một giải thuật có thể yêu cầu một mảng có kích thước n, hoặc một ma trận có kích thước n x n. Trong trường hợp này, độ phức tạp không gian sẽ tương ứng là O(n) và O(n^2).

Ký Hiệu Big O, Big Omega, và Big Theta

Để biểu diễn độ phức tạp, chúng ta sử dụng các ký hiệu tiệm cận. Các ký hiệu này giúp chúng ta mô tả hành vi của giải thuật khi kích thước đầu vào tiến đến vô cùng.

Big O (O)

Big O biểu diễn cận trên của độ phức tạp. O(f(n)) có nghĩa là thời gian thực thi (hoặc không gian sử dụng) của giải thuật không tăng nhanh hơn f(n), *trong trường hợp xấu nhất*.

Ví dụ, nếu một giải thuật có độ phức tạp O(n^2), thì thời gian thực thi của nó sẽ không bao giờ tăng nhanh hơn n^2. Nó có thể tăng chậm hơn, nhưng không bao giờ nhanh hơn. Tư duy một cách trực quan, Big O giống như một "trần nhà".

Big Omega (Ω)

Big Omega biểu diễn cận dưới của độ phức tạp. Ω(f(n)) có nghĩa là thời gian thực thi (hoặc không gian sử dụng) của giải thuật luôn lớn hơn hoặc bằng f(n), *trong trường hợp tốt nhất*.

Ví dụ, nếu một giải thuật có độ phức tạp Ω(n), thì thời gian thực thi của nó sẽ luôn lớn hơn hoặc bằng n. Tư duy một cách trực quan, Big Omega giống như một "sàn nhà".

Big Theta (Θ)

Big Theta biểu diễn cả cận trên và cận dưới của độ phức tạp. Θ(f(n)) có nghĩa là thời gian thực thi (hoặc không gian sử dụng) của giải thuật tăng trưởng với tốc độ tương tự như f(n).

Ví dụ, nếu một giải thuật có độ phức tạp Θ(n log n), thì thời gian thực thi của nó sẽ tăng trưởng tỉ lệ với n log n. Big Theta biểu diễn một "ranh giới chặt chẽ" cho độ phức tạp.

Ví Dụ Tính Độ Phức Tạp trong Java

Chúng ta sẽ xem xét một số ví dụ đơn giản bằng Java để minh họa cách tính độ phức tạp.

Ví dụ 1: Duyệt Mảng

public static void printArray(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
      System.out.println(arr[i]);
    }
  }

Trong ví dụ này, chúng ta duyệt qua từng phần tử của mảng một lần. Số lượng phép toán (System.out.println) tỉ lệ tuyến tính với kích thước của mảng (n). Do đó, độ phức tạp thời gian là O(n).

Ví dụ 2: Tìm Phần Tử Lớn Nhất

public static int findMax(int[] arr) {
    int max = arr[0];
    for (int i = 1; i < arr.length; i++) {
      if (arr[i] > max) {
        max = arr[i];
      }
    }
    return max;
  }

Tương tự như ví dụ trước, chúng ta duyệt qua mảng một lần. Số lượng phép so sánh (arr[i] > max) tỉ lệ tuyến tính với kích thước của mảng. Độ phức tạp thời gian là O(n).

Ví dụ 3: Mảng Hai Chiều

public static void printMatrix(int[][] matrix) {
    for (int i = 0; i < matrix.length; i++) {
      for (int j = 0; j < matrix[i].length; j++) {
        System.out.println(matrix[i][j]);
      }
    }
  }

Ở đây, chúng ta duyệt qua một ma trận hai chiều. Nếu ma trận có kích thước n x m, thì chúng ta sẽ thực hiện n * m phép toán. Nếu n = m, thì độ phức tạp thời gian là O(n^2).

Ví dụ 4: Tìm Kiếm Nhị Phân

public static int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    while (left <= right) {
      int mid = left + (right - left) / 2;
      if (arr[mid] == target) {
        return mid;
      } else if (arr[mid] < target) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
    return -1;
  }

Tìm kiếm nhị phân chia đôi không gian tìm kiếm ở mỗi bước. Số lượng bước tối đa là log2(n). Do đó, độ phức tạp thời gian là O(log n).

Ví dụ 5: Sắp Xếp Nổi Bọt (Bubble Sort)

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    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+1] and arr[j]
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

Sắp xếp nổi bọt sử dụng hai vòng lặp lồng nhau để so sánh và hoán đổi các phần tử. Vòng lặp bên ngoài chạy n-1 lần và vòng lặp bên trong chạy n-i-1 lần. Do đó, số lượng phép so sánh là khoảng (n^2)/2, dẫn đến độ phức tạp thời gian là O(n^2).

Tổng Kết

Trong bài viết này, chúng ta đã tìm hiểu về phân tích hiệu năng giải thuật, tập trung vào độ phức tạp thời gian và không gian. Chúng ta đã giải thích các ký hiệu Big O, Big Omega, và Big Theta, và minh họa cách tính độ phức tạp thông qua các ví dụ đơn giản bằng Java. Việc hiểu rõ độ phức tạp của giải thuật là vô cùng quan trọng để xây dựng các ứng dụng hiệu quả. Hãy tiếp tục khám phá các chủ đề khác trong series này để nâng cao kiến thức của bạn về cấu trúc dữ liệu và giải thuật!