Đại O và biểu diễn tiệm cận

Khi tính toán độ phức tạp thời gian, chúng ta không cần phải xác định chính xác số lần thực hiện của chương trình. Việc này có thể rất phức tạp (vì mỗi câu lệnh có thể được biên dịch thành số lượng khác nhau các lệnh). Thay vào đó, chúng ta chỉ cần ước lượng số lần thực hiện đại diện cho mức tăng trưởng. Độ phức tạp thường được biểu diễn bằng phương pháp Đại O tiệm cận.

• Trong hàm T(N) biểu diễn độ phức tạp, chỉ giữ lại bậc cao nhất và bỏ qua các bậc thấp hơn, vì khi N tăng lên, ảnh hưởng của các bậc thấp trở nên không đáng kể.
• Nếu bậc cao nhất tồn tại và hệ số không phải là 1, hãy loại bỏ hệ số này, vì khi N tăng lên, hệ số cũng trở nên không quan trọng.
• Nếu T(N) không chứa N mà chỉ chứa hằng số, thay thế tất cả các hằng số cộng bởi 1.

Ví dụ 1: Hàm strchr

const char * strchr (const char * str, int character) {
    const char* p_begin = str;
    while (*p_begin != character) {
        if (*p_begin == '\0') return NULL;
        p_begin++;
    }
    return p_begin;
}

Số lần thực hiện cơ bản: - Nếu ký tự cần tìm ở vị trí đầu tiên: T(N) = 1 - Nếu ký tự cần tìm ở vị trí cuối cùng: T(N) = N - Nếu ký tự cần tìm ở giữa: T(N) = N/2 Vậy, độ phức tạp thời gian của strchr là: - Tốt nhất: O(1) - Xấu nhất: O(N) - Trung bình: O(N)

Ví dụ 2: Bubble Sort

void BubbleSort(int* a, int n) {
    assert(a);
    for (size_t end = n; end > 0; --end) {
        int exchange = 0;
        for (size_t i = 1; i < end; ++i) {
            if (a[i-1] > a[i]) {
                Swap(&a[i-1], &a[i]);
                exchange = 1;
            }
        }
        if (exchange == 0) break;
    }
}

Số lần thực hiện: - Nếu mảng đã sắp xếp: T(N) = N - Nếu mảng sắp xếp giảm dần: T(N) = (N * (N + 1)) / 2 - Trung bình: T(N) = N^2 / 2 Vậy, độ phức tạp thời gian của Bubble Sort là: - Tốt nhất: O(N) - Xấu nhất: O(N^2)

Ví dụ 3: Hàm func5

void func5(int n) {
    int cnt = 1;
    while (cnt < n) {
        cnt *= 2;
    }
}

Số lần thực hiện: - Khi n = 2, số lần thực hiện là 1 - Khi n = 4, số lần thực hiện là 2 - Khi n = 16, số lần thực hiện là 4 Giả sử số lần thực hiện là x, thì 2^x = n Vậy, số lần thực hiện: x = log2(n) Vậy, độ phức tạp thời gian của func5 là: O(log n)

So sánh các độ phức tạp thông thường