Khóa học CTDL và GT

Bài 1.1. Phân tích độ phức tạp thuật toán: O(1), O(n), O(n²), O(log n)

Chào mừng các bạn quay trở lại với chuỗi bài viết về Cấu trúc dữ liệu và Giải thuật! Sau khi đã nắm được cái nhìn tổng quan về tầm quan trọng của CTDL&GT trong bài trước, chúng ta sẽ cùng nhau lặn sâu vào một trong những khái niệm quan trọng nhất khi đánh giá và so sánh các giải thuật: Độ phức tạp thuật toán (Algorithm Complexity), cụ thể là Độ phức tạp về thời gian (Time Complexity).

Tại sao chúng ta cần quan tâm đến độ phức tạp? Khi giải quyết một vấn đề, thường có nhiều cách (nhiều thuật toán) khác nhau để đạt được kết quả. Vấn đề là, không phải thuật toán nào cũng hiệu quả như nhau, đặc biệt là khi dữ liệu đầu vào trở nên lớn. Một thuật toán có thể chạy rất nhanh với dữ liệu nhỏ, nhưng lại trở nên ì ạch hoặc thậm chí không thể sử dụng được khi dữ liệu tăng lên đáng kể. Phân tích độ phức tạp giúp chúng ta dự đoán và hiểu rõ hành vi của thuật toán khi kích thước đầu vào (n) thay đổi, từ đó chọn ra giải pháp tối ưu nhất.

Chúng ta sẽ tập trung vào ký hiệu Big O (O), một cách tiêu chuẩn để mô tả giới hạn trên (worst-case scenario) của thời gian chạy thuật toán dựa trên kích thước đầu vào n. Ký hiệu Big O giúp chúng ta bỏ qua các hằng số và các thành phần bậc thấp, chỉ tập trung vào tốc độ tăng trưởng của thời gian chạy khi n tiến tới vô cùng. Đây là thước đo độc lập với phần cứng máy tính hay ngôn ngữ lập trình cụ thể.

Hãy cùng khám phá các độ phức tạp Big O phổ biến nhất!

1. O(1) - Độ phức tạp hằng số (Constant Time)

Độ phức tạp O(1) có nghĩa là thời gian thực thi của thuật toán là không đổi, không phụ thuộc vào kích thước của dữ liệu đầu vào n. Bất kể dữ liệu có nhỏ hay lớn đến đâu, thuật toán vẫn hoàn thành trong một lượng thời gian gần như như nhau.

Các thao tác có độ phức tạp O(1) thường là các thao tác cơ bản, trực tiếp, không lặp lại hay đệ quy dựa trên kích thước n.

• Ví dụ:

  • Truy cập một phần tử tại vị trí cố định trong mảng hoặc vector.
  • Thực hiện các phép toán số học đơn giản (cộng, trừ, nhân, chia).
  • Gán giá trị cho một biến.
  • Gọi một hàm có thời gian chạy O(1).

• Minh họa bằng C++:

#include <iostream>
#include <vector>

int main() {
    std::vector<int> data = {10, 20, 30, 40, 50};
    int index = 2; // Vị trí cố định mà chúng ta muốn truy cập

    // Thao tác 1: Truy cập phần tử tại chỉ mục 'index'
    // Giả sử 'index' luôn hợp lệ trong phạm vi mảng/vector
    // Đây là một thao tác O(1)
    if (index >= 0 && index < data.size()) {
        int value = data[index];
        std::cout << "Gia tri tai vi tri " << index << ": " << value << std::endl;
    } else {
        std::cout << "Vi tri khong hop le!" << std::endl;
    }

    // Thao tác 2: Thực hiện các phép toán số học đơn giản
    // Đây cũng là các thao tác O(1)
    int a = 5, b = 10;
    int sum = a + b;
    int product = a * b;
    std::cout << "Tong: " << sum << ", Tich: " << product << std::endl;

    return 0;
}

• Giải thích code: Trong ví dụ trên, việc truy cập data[index] mất một lượng thời gian cố định, bất kể vector data có 5 phần tử hay 5 triệu phần tử. Tương tự, các phép toán a + b hay a * b cũng chỉ mất một số lượng bước xử lý nhất định, không phụ thuộc vào bất kỳ kích thước đầu vào n nào liên quan đến bài toán lớn hơn. Do đó, các thao tác này có độ phức tạp là O(1).

2. O(n) - Độ phức tạp tuyến tính (Linear Time)

Độ phức tạp O(n) có nghĩa là thời gian thực thi của thuật toán tăng trưởng tuyến tính theo kích thước của dữ liệu đầu vào n. Nếu kích thước đầu vào tăng gấp đôi, thời gian chạy sẽ xấp xỉ tăng gấp đôi.

Thuật toán O(n) thường phải xử lý từng phần tử của dữ liệu đầu vào một lần (hoặc một số lần cố định).

• Ví dụ:

  • Duyệt qua tất cả các phần tử trong một mảng hoặc vector để tìm kiếm một giá trị (tìm kiếm tuyến tính).
  • Tính tổng hoặc trung bình của tất cả các phần tử trong một mảng.
  • In tất cả các phần tử của một danh sách.

• Minh họa bằng C++:

#include <iostream>
#include <vector>
#include <numeric> // Thu vien ho tro cac phep toan tren day so

int main() {
    // Giả sử data có n phần tử. Ở đây n=10.
    std::vector<int> data = {1, 5, 3, 8, 2, 9, 4, 7, 6, 10};

    // Thao tác 1: Tính tổng tất cả các phần tử trong vector
    // Cần duyệt qua TẤT CẢ các phần tử một lần
    // Đây là thao tác O(n)
    long long sum = 0;
    for (size_t i = 0; i < data.size(); ++i) {
        sum += data[i]; // Một phép cộng và gán cho mỗi phần tử
    }
    std::cout << "Tong cac phan tu: " << sum << std::endl;

    // Minh họa khác: Tìm kiếm tuyến tính
    // Trong trường hợp xấu nhất, chúng ta phải kiểm tra TẤT CẢ các phần tử
    // Đây là thao tác O(n) trong trường hợp xấu nhất (worst-case)
    int target = 7;
    bool found = false;
    for (size_t i = 0; i < data.size(); ++i) {
        if (data[i] == target) { // So sánh một lần cho mỗi phần tử
            found = true;
            break; // Tìm thấy thì dừng, nhưng worst-case vẫn là O(n)
        }
    }
    if (found) {
        std::cout << target << " duoc tim thay trong vector." << std::endl;
    } else {
        std::cout << target << " khong duoc tim thay trong vector." << std::endl;
    }

    return 0;
}

• Giải thích code: Trong cả hai ví dụ (tính tổng và tìm kiếm tuyến tính), chúng ta sử dụng một vòng lặp duyệt qua vector data. Số lần lặp của vòng lặp tỷ lệ thuận với số lượng phần tử trong vector (kích thước n). Với mỗi lần lặp, chúng ta thực hiện một số thao tác cố định (phép cộng/gán hoặc phép so sánh). Do đó, tổng số thao tác sẽ tăng tuyến tính theo n. Nếu vector có 1000 phần tử, nó sẽ mất khoảng 1000 bước. Nếu có 2000 phần tử, khoảng 2000 bước. Điều này thể hiện độ phức tạp O(n).

3. O(n²) - Độ phức tạp bình phương (Quadratic Time)

Độ phức tạp O(n²) có nghĩa là thời gian thực thi của thuật toán tăng trưởng bình phương theo kích thước của dữ liệu đầu vào n. Nếu kích thước đầu vào tăng gấp đôi, thời gian chạy sẽ xấp xỉ tăng gấp bốn lần (2²).

Thuật toán O(n²) thường xuất hiện khi có các vòng lặp lồng nhau, trong đó vòng lặp bên trong lặp lại dựa trên kích thước n cho mỗi lần lặp của vòng lặp bên ngoài (cũng lặp lại dựa trên n).

• Ví dụ:

  • Các thuật toán sắp xếp đơn giản như Bubble Sort, Selection Sort, Insertion Sort (trong trường hợp xấu nhất hoặc trung bình).
  • In tất cả các cặp phần tử có thể có trong một danh sách.
  • So sánh mọi phần tử với mọi phần tử khác trong một tập dữ liệu.

• Minh họa bằng C++:

#include <iostream>
#include <vector>
#include <algorithm> // Cho std::swap

int main() {
    // Giả sử data có n phần tử. Ở đây n=5.
    std::vector<int> data = {5, 2, 8, 1, 9};

    // Thao tác 1: In tất cả các cặp phần tử có thể có
    // Cần 2 vòng lặp lồng nhau, mỗi vòng lặp duyệt qua n phần tử
    // Tổng số cặp là n * n
    // Đây là thao tác O(n²)
    std::cout << "In tat ca cac cap phan tu (O(n^2)):" << std::endl;
    for (size_t i = 0; i < data.size(); ++i) {
        for (size_t j = 0; j < data.size(); ++j) {
            std::cout << "(" << data[i] << ", " << data[j] << ") ";
        }
        std::cout << std::endl;
    }

    // Thao tác 2: Minh họa cấu trúc lồng nhau dẫn đến O(n^2)
    // Đây là một pass đơn giản của Bubble Sort hoặc Selection Sort inner loop
    // Thuật toán sắp xếp Bubble Sort/Selection Sort HOÀN CHỈNH có độ phức tạp O(n^2)
    std::vector<int> sort_data = {5, 2, 8, 1, 9};
    std::cout << "\nSap xep (minh hoa cau truc O(n^2) cua Bubble/Selection Sort):" << std::endl;
    // Vòng lặp ngoài chạy n-1 lần (hoặc n lần tùy cách cài đặt)
    for (size_t i = 0; i < sort_data.size() - 1; ++i) {
        // Vòng lặp trong chạy khoảng n-1-i lần
        // Tổng số lần lặp của vòng trong qua toàn bộ quá trình là ~ n * (n/2) = O(n^2)
        for (size_t j = i + 1; j < sort_data.size(); ++j) {
            // So sánh và hoán đổi là các thao tác O(1)
            if (sort_data[i] > sort_data[j]) {
                std::swap(sort_data[i], sort_data[j]);
            }
        }
    }
     std::cout << "Vector sau khi sap xep (Bubble Sort): ";
     for(int val : sort_data) {
         std::cout << val << " ";
     }
     std::cout << std::endl;


    return 0;
}

• Giải thích code: Ví dụ in các cặp phần tử là minh họa rõ ràng nhất cho O(n²). Vòng lặp ngoài chạy n lần. Với mỗi lần lặp của vòng ngoài, vòng lặp bên trong lại chạy n lần. Tổng số lần thực hiện các thao tác bên trong (ví dụ: in cặp số) là n * n = n². Ví dụ sắp xếp Bubble Sort cũng tương tự. Vòng lặp ngoài chạy gần n lần. Vòng lặp bên trong (để tìm phần tử nhỏ nhất hoặc đẩy phần tử lớn nhất về cuối) chạy giảm dần từ n-1, n-2, ... đến 1. Tổng số thao tác so sánh/hoán đổi là khoảng (n-1) + (n-2) + ... + 1 = n*(n-1)/2. Khi n rất lớn, hằng số 1/2 và số hạng bậc thấp n/2 bị bỏ qua trong ký hiệu Big O, chỉ còn lại n². Do đó, độ phức tạp là O(n²).

4. O(log n) - Độ phức tạp logarit (Logarithmic Time)

Độ phức tạp O(log n) có nghĩa là thời gian thực thi của thuật toán tăng trưởng rất chậm theo kích thước của dữ liệu đầu vào n. Thay vì xử lý từng phần tử, thuật toán O(log n) thường hoạt động bằng cách liên tục chia đôi (hoặc chia thành một phần cố định) không gian tìm kiếm hoặc phạm vi xử lý.

logarit cơ số 2 của n (ký hiệu log₂n hoặc thường chỉ là log n trong phân tích thuật toán) là số lần bạn phải chia đôi n để nhận được 1. Ví dụ: log₂8 = 3 vì 8 -> 4 -> 2 -> 1 (3 lần chia đôi). log₂1024 = 10. log₂1.048.576 = 20. Bạn có thể thấy, n tăng lên rất nhanh, nhưng log n chỉ tăng lên rất chậm. Đây là độ phức tạp rất hiệu quả cho dữ liệu lớn.

• Ví dụ:

  • Tìm kiếm nhị phân (Binary Search) trên một mảng hoặc danh sách đã được sắp xếp.
  • Tìm kiếm, thêm, xóa một phần tử trong cấu trúc dữ liệu cân bằng như cây tìm kiếm nhị phân (Balanced Binary Search Tree).

• Minh họa bằng C++:

#include <iostream>
#include <vector>
#include <algorithm> // Cho std::binary_search (cần mảng/vector đã sắp xếp)

// Cài đặt Binary Search thủ công để hiểu rõ hơn
// Trả về chỉ mục của target nếu tìm thấy, ngược lại trả về -1
int binarySearch(const std::vector<int>& sorted_data, int target) {
    int left = 0; // Chỉ mục bên trái của phạm vi tìm kiếm
    int right = sorted_data.size() - 1; // Chỉ mục bên phải

    // Lặp cho đến khi phạm vi tìm kiếm hợp lệ (left <= right)
    while (left <= right) {
        // Tính chỉ mục trung tâm
        // Cách tính an toàn hơn để tránh tràn số với số nguyên lớn
        int mid = left + (right - left) / 2;

        // So sánh phần tử tại mid với target
        if (sorted_data[mid] == target) {
            return mid; // Tìm thấy target, trả về chỉ mục
        } else if (sorted_data[mid] < target) {
            // target lớn hơn phần tử ở mid, bỏ qua nửa trái (bao gồm cả mid)
            // Tìm kiếm trong nửa phải: phạm vi mới từ mid + 1 đến right
            left = mid + 1;
        } else { // sorted_data[mid] > target
            // target nhỏ hơn phần tử ở mid, bỏ qua nửa phải (bao gồm cả mid)
            // Tìm kiếm trong nửa trái: phạm vi mới từ left đến mid - 1
            right = mid - 1;
        }
        // Sau mỗi lần lặp, kích thước phạm vi tìm kiếm bị CHIA ĐÔI
    }

    // Nếu vòng lặp kết thúc mà không tìm thấy, trả về -1
    return -1;
}

int main() {
    // Binary Search chỉ hoạt động trên dữ liệu ĐÃ ĐƯỢC SẮP XẾP
    std::vector<int> data = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100}; // n = 10

    int target1 = 70;
    int target2 = 35;

    // Tìm kiếm target1 bằng cài đặt thủ công
    int index1 = binarySearch(data, target1);
    if (index1 != -1) {
        std::cout << "Muc tieu " << target1 << " duoc tim thay tai vi tri " << index1 << " (O(log n))." << std::endl;
    } else {
        std::cout << "Muc tieu " << target1 << " khong duoc tim thay." << std::endl;
    }

    // Tìm kiếm target2 bằng cài đặt thủ công
    int index2 = binarySearch(data, target2);
     if (index2 != -1) {
        std::cout << "Muc tieu " << target2 << " duoc tim thay tai vi tri " << index2 << " (O(log n))." << std::endl;
    } else {
        std::cout << "Muc tieu " << target2 << " khong duoc tim thay." << std::endl;
    }

    // Sử dụng hàm binary_search có sẵn trong STL C++ (chỉ trả về true/false)
    // std::binary_search cũng có độ phức tạp O(log n)
    bool found_stl = std::binary_search(data.begin(), data.end(), target1);
    std::cout << "Su dung std::binary_search cho " << target1 << ": " << (found_stl ? "Tim thay" : "Khong tim thay") << std::endl;


    return 0;
}

• Giải thích code: Hàm binarySearch hoạt động trên một vector đã sắp xếp. Nó bắt đầu với một phạm vi tìm kiếm bao gồm toàn bộ vector (từ left đến right). Trong mỗi lần lặp của vòng while:

  1. Nó kiểm tra phần tử ở vị trí mid (giữa phạm vi).
  2. Nếu sorted_data[mid] bằng target, chúng ta tìm thấy và dừng lại.
  3. Nếu sorted_data[mid] nhỏ hơn target, chúng ta biết rằng target (nếu có) phải nằm ở nửa bên phải của mid (vì mảng đã sắp xếp). Chúng ta loại bỏ nửa bên trái và tiếp tục tìm kiếm trong nửa phải bằng cách cập nhật left = mid + 1.
  4. Nếu sorted_data[mid] lớn hơn target, chúng ta biết rằng target (nếu có) phải nằm ở nửa bên trái của mid. Chúng ta loại bỏ nửa bên phải và tiếp tục tìm kiếm trong nửa trái bằng cách cập nhật right = mid - 1.

  Mỗi lần lặp, kích thước của phạm vi tìm kiếm giảm đi một nửa. Số lần bạn có thể chia đôi n cho đến khi còn 1 phần tử là log₂n. Do đó, số lần lặp của vòng while và tổng số thao tác tỷ lệ thuận với log n. Điều này giải thích tại sao Binary Search có độ phức tạp O(log n), biến nó thành một thuật toán tìm kiếm cực kỳ hiệu quả trên dữ liệu lớn và đã được sắp xếp.

5. So sánh các Độ phức tạp

Bây giờ chúng ta đã xem xét các độ phức tạp phổ biến, hãy cùng so sánh chúng để thấy rõ sự khác biệt về hiệu suất khi n tăng lên:

O(1) < O(log n) < O(n) < O(n²)

• O(1): Tốt nhất. Thời gian không tăng theo n.
• O(log n): Rất tốt. Thời gian tăng rất chậm. Tuyệt vời cho các bài toán "chia để trị" trên dữ liệu đã sắp xếp.
• O(n): Tốt. Thời gian tăng tuyến tính. Chấp nhận được cho nhiều bài toán khi cần xử lý từng phần tử.
• O(n²): Kém hiệu quả hơn. Thời gian tăng rất nhanh. Cần cẩn trọng với các thuật toán O(n²) khi làm việc với dữ liệu lớn vì thời gian chạy có thể trở nên không thể chấp nhận được.

Hãy xem bảng so sánh giả định số lượng thao tác với các giá trị khác nhau của n:

Lưu ý: Các giá trị này là ước tính dựa trên n hoặc log₂n, bỏ qua hằng số. Mục đích là để cho thấy tốc độ tăng trưởng tương đối.

Bạn có thể thấy rõ, khi n đạt tới 1 triệu, một thuật toán O(n²) cần tới hàng nghìn tỷ thao tác, trong khi O(n) chỉ cần 1 triệu, O(log n) chỉ khoảng 20, và O(1) vẫn là một hằng số nhỏ. Đây chính là sức mạnh thực sự của việc phân tích Big O: nó giúp chúng ta hiểu cách thuật toán sẽ mở rộng (scale) khi dữ liệu tăng lên.

Tóm lại

Phân tích độ phức tạp thuật toán, đặc biệt là độ phức tạp về thời gian với ký hiệu Big O, là một kỹ năng thiết yếu đối với mọi lập trình viên. Nó cho phép chúng ta:

1. Dự đoán hiệu suất: Ước tính thời gian chạy của thuật toán với dữ liệu lớn mà không cần thực sự chạy code.
2. So sánh thuật toán: Lựa chọn thuật toán hiệu quả nhất trong số các giải pháp khả thi cho cùng một vấn đề.
3. Tối ưu hóa code: Nhận biết các phần của thuật toán gây tốn thời gian nhất và tập trung vào việc cải thiện chúng.

Chúng ta đã đi qua các độ phức tạp cơ bản nhất: O(1), O(n), O(n²), và O(log n). Hiểu được ý nghĩa và cách nhận biết chúng trong code là bước đầu tiên và quan trọng nhất trên hành trình chinh phục Cấu trúc dữ liệu và Giải thuật.

Bài tập ví dụ:

Truy vấn dãy số

Trong một chuyến khám phá dãy ngân hà xa xôi, FullHouse Dev đã tình cờ bắt gặp một bài toán thú vị về các dãy số nhị phân. Để có thể tiếp tục hành trình, họ cần phải giải quyết bài toán này. Với kinh nghiệm xử lý dữ liệu của mình, FullHouse Dev đã bắt tay vào việc phân tích và giải quyết vấn đề.

Bài toán

Cho \(Q\) truy vấn, mỗi truy vấn gồm ba số \(L\), \(R\) và \(X\). Nhiệm vụ là tìm số lượng số nguyên trong đoạn từ \(L\) đến \(R\) mà có bit thứ \(X\) (tính từ phải qua, bắt đầu từ 1) bằng 1.

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(Q\) - số lượng truy vấn
• \(Q\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(L\), \(R\) và \(X\)

OUTPUT FORMAT:

• Với mỗi truy vấn, in ra số lượng số nguyên trong đoạn \([L,R]\) thỏa mãn điều kiện đề bài

Ràng buộc:

• \(1 \leq Q \leq 10^5\)
• \(1 \leq L \leq R \leq 10^9\)
• \(1 \leq X \leq 31\)

Ví dụ

INPUT

1
2 6 2

OUTPUT

3

Giải thích

Biểu diễn nhị phân của các số trong đoạn \([2,6]\) như sau:

• 2: 10
• 3: 11
• 4: 100
• 5: 101
• 6: 110

Có 3 số có bit thứ 2 bằng 1 là: 2, 3 và 6. Do đó, kết quả là 3. Tuyệt vời! Đây là hướng giải ngắn gọn cho bài toán "Truy vấn dãy số" bằng C++:

1. Phân tích yêu cầu: Cần đếm số lượng số trong đoạn [L, R] mà có bit thứ X (tính từ phải, bắt đầu từ 1) bằng 1. Truy vấn nhiều lần (Q lần). Ràng buộc R đến 10^9 cho thấy cần giải pháp hiệu quả hơn duyệt từng số.

2. Chuyển đổi bài toán: Bài toán đếm trên đoạn [L, R] có thể được chuyển thành đếm trên đoạn [1, R] trừ đi đếm trên đoạn [1, L-1]. Tức là, nếu ta có hàm CountSetBits(N, X) đếm số lượng số nguyên trong đoạn [1, N] mà bit thứ X bằng 1, thì kết quả cho truy vấn (L, R, X) sẽ là CountSetBits(R, X) - CountSetBits(L - 1, X).

3. Thiết kế hàm CountSetBits(N, X): Đây là phần cốt lõi. Ta cần đếm các số từ 1 đến N có bit thứ X bằng 1.

   • Bit thứ X (1-indexed) tương ứng với bit thứ X-1 (0-indexed). Giá trị của bit này là 2^(X-1).
   • Mẫu bit thứ X-1 lặp lại theo chu kỳ. Chu kỳ có độ dài 2^X. Trong mỗi chu kỳ đầy đủ (ví dụ từ 0 đến 2^X - 1), có chính xác 2^(X-1) số mà bit thứ X-1 bằng 1 (các số từ 2^(X-1) đến 2^X - 1).
   • Để đếm đến N, ta có thể đếm số chu kỳ đầy đủ trong đoạn [0, N] (hoặc [1, N], dễ hơn nếu xét [0, N] với độ dài N+1). Số chu kỳ đầy đủ là (N + 1) / (2^X). Mỗi chu kỳ đóng góp 2^(X-1) số.
   • Phần còn lại sau các chu kỳ đầy đủ là (N + 1) % (2^X) số. Ta xét các số này. Bit thứ X-1 bằng 1 trong phần này nếu vị trí của chúng (tính từ đầu chu kỳ) nằm trong khoảng [2^(X-1), 2^X - 1]. Số lượng các số như vậy trong phần dư là max(0LL, ((N + 1) % (2^X)) - (2^(X-1))).
   • Tổng số lượng số trong [0, N] có bit thứ X-1 bằng 1 sẽ là: ((N + 1) / (1LL << X)) * (1LL << (X - 1)) + max(0LL, ((N + 1) % (1LL << X)) - (1LL << (X - 1))).
   • Vì 0 không có bit thứ X bằng 1 với X >= 1, nên đếm trong [0, N] tương đương đếm trong [1, N].

4. Kiểu dữ liệu: Sử dụng long long cho L, R, và kết quả đếm để tránh tràn số, vì N có thể lên đến 10^9 và tổng số có thể vượt quá giới hạn của int.

5. Thực hiện:

   • Đọc Q.
   • Lặp Q lần:
     • Đọc L, R, X.
     • Tính CountSetBits(R, X).
     • Tính CountSetBits(L - 1, X). (Lưu ý L-1 có thể là 0, hàm CountSetBits cần xử lý đúng với N=0).
     • In ra hiệu của hai giá trị trên.

Đây là logic chính để giải quyết bài toán một cách hiệu quả trong các ràng buộc cho phép.

Làm thêm nhiều bài tập miễn phí tại đây