1.3 Độ phức tạp thời gian

I. Quy mô dữ liệu theo độ phức tạp thời gian

Quy mô dữ liệu có thể giải được trong 1s: $10^6 \sim 10^7$

• Thuật toán $O(n^2)$ có thể xử lý quy mô dữ liệu cỡ $10^4$ (ước lượng bảo thủ: chắc chắn xử lý tốt các bài cỡ 1000).
• Thuật toán $O(n)$ có thể xử lý quy mô dữ liệu cỡ $10^8$ (ước lượng bảo thủ: chắc chắn xử lý tốt các bài cỡ $10^7$).
• Thuật toán $O(n log n)$ có thể xử lý quy mô dữ liệu cỡ $10^7$ (ước lượng bảo thủ: chắc chắn xử lý tốt các bài cỡ $10^6$).

Một vài ví dụ dễ gây nhầm lẫn:

void hello (int n){
    for( int sz = 1 ; sz < n ; sz += sz )
        for( int i = 1 ; i < n ; i ++ )
            cout << "Hello" << endl;
}

Đoạn code trên có độ phức tạp thời gian là $O(n log n)$, không phải $O(n^2)$.

bool isPrime (int n){
    if (num <= 1) return false;
    for( int x = 2 ; x * x <= n ; x ++ )
        if( n % x == 0 )
            return false;
    return true;
}

Đoạn code trên có độ phức tạp thời gian là $O(\sqrt{n})$, không phải $O(n)$.

Thêm một ví dụ nữa: có một mảng chuỗi; ta sắp xếp từng chuỗi theo thứ tự chữ cái, sau đó sắp xếp cả mảng chuỗi theo thứ tự từ điển. Độ phức tạp thời gian tổng của hai bước là bao nhiêu?

Nếu trả lời là $O(n \cdot n log n + n log n) = O(n^2 log n)$ thì sai. Độ dài chuỗi và độ dài mảng là hai biến độc lập, nên cần tính riêng. Giả sử độ dài chuỗi lớn nhất là $s$, trong mảng có $n$ chuỗi. Sắp xếp mỗi chuỗi có độ phức tạp $O(s log s)$, vậy sắp xếp tất cả chuỗi theo thứ tự chữ cái là $O(n \cdot s log s)$.

Sắp xếp cả mảng chuỗi theo thứ tự từ điển có độ phức tạp là $O(s \cdot n log n)$. Trong thuật toán sắp xếp, $O(n log n)$ là số lần so sánh; nếu so sánh số nguyên thì mỗi lần là $O(1)$. Nhưng so sánh chuỗi theo thứ tự từ điển là $O(s)$. Vì vậy, sắp xếp mảng chuỗi theo thứ tự từ điển là $O(s \cdot n log n)$. Do đó, tổng độ phức tạp là $O(n \cdot s log s) + O(s \cdot n log n) = O(n \cdot s log s + s \cdot n log n) = O(n \cdot s \cdot (log s + log n)) = O(n \cdot s \cdot log(n \cdot s))$.

II. Độ phức tạp không gian

Lời gọi đệ quy có “chi phí” bộ nhớ: thuật toán đệ quy cần lưu thông tin ngăn xếp đệ quy (recursion stack), vì vậy độ phức tạp không gian thường cao hơn so với thuật toán không đệ quy.

int sum( int n ){
    assert( n >= 0 )
    int ret = 0;
    for ( int i = 0 ; i <= n ; i ++ )
        ret += i;
    return ret;
}

Thuật toán trên có độ phức tạp thời gian $O(n)$, độ phức tạp không gian $O(1)$.

int sum( int n ){
    assert( n >= 0 )
    if ( n == 0 )
        return 0;
    return n + sum( n - 1 );
}

Thuật toán trên có độ phức tạp thời gian $O(n)$, độ phức tạp không gian $O(n)$.

III. Độ phức tạp thời gian của đệ quy

1. Chỉ có một lần gọi đệ quy

Nếu trong hàm đệ quy chỉ gọi lại chính nó một lần, và độ sâu đệ quy là depth, mỗi lần gọi tốn thời gian $T$, thì tổng độ phức tạp thời gian là $O(T \cdot depth)$.

Ví dụ:

int binarySearch(int arr[], int l, int r, int target){
	if( l > r )
	    return -1;
    int mid = l + ( r - l ) / 2; // Chống tràn
    if(arr[mid] == target)
        return mid;
    else if (arr[mid] > target)
        return binarySearch(arr,l,mid-1,target);
    else
        return binarySearch(arr,mid+1,r,target);
}

Trong hiện thực đệ quy của tìm kiếm nhị phân (Binary Search), hàm chỉ gọi lại chính nó. Độ sâu đệ quy là $log n$, và mỗi lần gọi tốn $O(1)$, nên độ phức tạp thời gian là $O(log n)$.

2. Có nhiều lần gọi đệ quy

Với trường hợp có nhiều lần gọi đệ quy, ta cần xem số lượng lời gọi được tạo ra. Thường có thể vẽ cây đệ quy (recursion tree) để phân tích. Ví dụ:

int f(int n){
    assert( n >= 0 );
    if( n == 0 )
        return 1;
    return f( n - 1 ) + f ( n - 1 );
}

Tổng số lần gọi đệ quy trong trường hợp này là

.

Với phân tích độ phức tạp của các bài đệ quy phức tạp hơn, hãy tham khảo Định lý Master (Master Theorem). Định lý này đưa ra kết luận đúng cho nhiều trường hợp phức tạp khác nhau.