Bảng độ phức tạp của các thuật toán năm 2024

Question

Cách tính độ phức tạp của một số giải thuật đơn giản.

Nội dung chính Show

2. Phân tích thuật toán
2.1. Mô hình RAM
2.1.1 Độ phức tạp theo thời gian
2.1.2 Cách xác định độ phức tạp theo thời gian
2.2.1. Giới thiệu về một số hàm số tăng cơ bản
2.2.1.2. Hàm số tuyến tính
2.2.1.3 Hàm số mũ

QUY TẮC XÁC ĐỊNH ĐỘ PHỨC TẠP

• Độ phức tạp tính toán của giải thuật: O(f(n))

• Việc xác định độ phức tạp tính toán của giải thuật trong thực tế có thể tính bằng một số quy tắc đơn giản sau:

– Quy tắc bỏ hằng số:

T(n) = O(c.f(n)) = O(f(n)) với c là một hằng số dương

– Quy tắc lấy max:

T(n) = O(f(n)+ g(n)) = O(max(f(n), g(n)))

– Quy tắc cộng:

T1(n) = O(f(n)) T2(n) = O(g(n))

T1(n) + T2(n) = O(f(n) + g(n))

– Quy tắc nhân:

Đoạn chương trình có thời gian thực hiện T(n)=O(f(n))

Nếu thực hiện k(n) lần đoạn chương trình với k(n) = O(g(n)) thì độ phức tạp sẽ là O(g(n).f(n))

PHÉP TOÁN TÍCH CỰC (BEST PROXY)

• Trong một thuật toán, ta chú ý đặc biệt đến một phép toán gọi là phép toán tích cực. Đó là phép toán mà số lần thực hiện không ít hơn các phép toán khác

• Ví dụ 1:

s = 0;

for (i=0; i<=n;i++){

p =1;

for (j=1;j<=i;j++)

p=p * x / j;

s = s+p;

}

Phép toán tích cực là p = p * x / j

Số lần thực hiện phép toán này là

0+1+2+…+n = n(n-1)/2 = n2/2 – n/2

\=> Vậy độ phức tạp là O(n2/2 – n/2)

\= O(n2/2) sử dụng quy tắc lấy max

\= O(n2) sử dụng quy tắc bỏ hằng số

• Ví dụ 2:

s = 1; p = 1;

for (i=1;i<=n;i++) {

p = p * x / i;

s = s + p;

}

Phép toán tích cực là p = p * x / i

Số lần thực hiện phép toán là n

\=> Vậy độ phức tạp của thuật toán là O(n)

• Ví dụ 3:

s=n*(n-1) /2;

\=> Độ phức tạp của thuật toán là O(1), nghĩa là thời gian tính toán không phụ thuộc vào n

• Ví dụ 4:

Thuật toán tính tổng các số từ 1 đến n

s=0;

for (i= 1;i<=n;i++)

s=s+i;

Vòng lặp lặp n lần phép gán s = s+i, nên thời gian tính toán tỉ lệ thuận với n, tức độ phức tạp là O(n).

Đối với một người làm về khoa học máy tính, thuật toán chắc chắn phải là một trong những khái niệm đầu tiên phải học.

Vậy thì thuật toán là gi?

Một thuật toán là một quá trình để thực hiện một task, thuật toán là ý tưởng bên trong của bất kì chương trình máy tính nghiêm chỉnh nào.

Ta có thể nói một thuật toán thì sẽ phải giải quyết một vấn đề nào đó và để giải quyết một vấn đề có thể có nhiều thuật toán khác nhau.

Ví dụ:

Vấn đề sắp xếp:

Input: Nhận vào một chuỗi các khoá x1, x2, x3, ...
Output: Sắp xếp lại thứ tự của chuỗi đầu vào sao cho theo thứ tự x1' <= x2' <= x3' ...

Để giải quyết vấn đề sắp xếp ta có các thuật toán sắp xếp: merge sort, quick sort, insertion sort, selection sort, …

2. Phân tích thuật toán

Có nhiều thuật toán để giải quyết một vấn đề.

Vì vậy sẽ nảy sinh vấn đề làm sao để lựa chọn thuật toán nào cho vấn đề nào.

Để giải quyết vấn đề đó chúng ta sẽ phải phân tích thuật toán.

Có hai công cụ quan trọng để đánh giá thuật toán: mô hình RAM, Big-O

2.1. Mô hình RAM

Mỗi thao tác đơn giản (+, -, *, /, if, call) tốn đúng một bước
Vòng lặp và hàm thì không phải là thao tác đơn giản và sẽ tốn nhiều hơn 1 bước để thực hiện
Mỗi thao tác truy xuất bộ nhớ sẽ tốn đúng một bước

Hiển nhiên chúng ta có thể thấy các điều kiện ở trên chỉ có tính tương đối và không đúng với thực tiễn.

Nhưng khi áp dụng mô hình RAM nó lại khiến cho việc phân tích thuật toán trở nên đơn giản và hiệu quả.

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

Khi áp dụng mô hình trên người ta thường sẽ để ý đến các trường hợp:

Trường hợp tốt nhất (best-case) là số lượng bước ít nhất cần để thực hiện thuật toán
Trường hợp tệ nhất (worst-case) là số lượng bước nhiều nhất cần để thực hiện thuật toán
Trường hợp trung bình (average-case) là số lượng bước trung bình để thực hiện thuật toán

Trường hợp tệ nhất đóng vai trò quan trọng trong thực tiễn và thường ta chỉ quan tâm đến nó mà bỏ qua hai trường hợp còn lại.

2.1.2 Cách xác định độ phức tạp theo thời gian

Độ phức tạp theo thời gian dùng để ước lượng thời gian cần thiết để thực thi giải thuật và được tính toán dựa vào số bước thực hiện các thao tác cơ bản.

Ví dụ: Hãy xác định thời gian thiện hiện thuật toán dưới đây

// Tính toán tìm phần tử lớn nhất trong mảng
Algorithm max(a):
    max ← a[0]
    for i = 1 to len(a)-1
        if a[i] > max
            max ← a[i]
    return max

Câu trả lời chính xác tuỳ thuộc vào nhiều yếu tố như là giá trị đầu vào, ngôn ngữ lập trình và môi trường thực thi, trình biên dịch, hệ điều hành và phần cứng, …

Vì vậy chúng ta thường chỉ muốn ước lượng thời gian thực thi thuật toán tương đối chỉ dựa vào thuật toán và giá trị đầu vào. Điều này có thể được thực hiện bằng cách chọn một thao tác cơ bản mà thuật toán lặp lại nhiều lần và tính toán độ phức tạp thời gian như là số thao tác cơ bản cần để thực hiện thuật toán với input array có độ dài n

Đối với thuật toán ở trên ta có thể chọn thao tác so sánh a[i] > max làm thao tác cơ bản.

Bởi vì phép toán so sánh được sử dụng xuyên suốt thuật toán nên là điều này sẽ cho phép phản ánh đúng đắn thời gian chạy của thuật toán
Hơn nữa thời gian thực hiện của phép so sánh là hằng số và không phụ thuộc vào kích thước của array.

2.1.2.1. Độ phức tạp thời gian tệ nhất (worst-case)

Xem xét thuật toán dưới này:

// Kiểm tra xem array a có chứa x.
Algorithm contains(a, x):
    for i = 0 to len(a)-1
        if x == a[i]
            return true
    return false

Phép toán so sánh x == a[i] có thể được dùng làm phép toán cơ bản trong trường hợp này. Tuy nhiên như chúng ta thấy trong trường hợp này số lượng phép toán so sánh được thực hiện không chỉ phụ thuộc vào số lượng phần tử array n mà còn phụ thộc vào giá trị của x và giá trị của các phần tử trong a.

Nếu không tìm thấy x thì số phép toán so sánh là n
Nếu x == a[0] thì chỉ cần một phép so sánh .

Vì lý do này mà thông thường ta sẽ chọn xác định trường hợp thời gian tệ nhất của thuật toán:

Cho T1(n), T2(n), … là thời gian thực thi của tất cả các giá trị có thể có của input kích thước n
Độ phức tạp thời gian trong trường hợp tệ nhất sẽ là W(n) = max(T1(n), T2(n), …)

Vì vậy độ phức thời gian trong trường hợp tệ nhất sẽ là n

2.1.2.2 Độ phức tạp thời gian trung bình (average-case)

Độ phức tạp thời gian trung bình thì ít phổ biến hơn, có thể được định nghĩa là số bước trung bình cần thiết để thực hiện thuật toán.

Cho T1(n), T2(n), … là thời gian thực thi của tất cả các giá tri có thể có của input kích thước n, và P1(n), P2(n), …là xác xuất của những input này.
Độ phức tạp thời gian trung bình (average-case) được định nghĩa là P1(n)T1(n) + P2(n)T2(n) + …

Độ phức tạp thời gian trung bình khó để tính toán và ý nghĩa của nó là chủ đề gây tranh cãi.

2.2. Big-O

Như ở trên ta có nói thời gian thực thi của một thuật toán phụ thuộc vào nhiều yếu tố và khó để xác định chính xác nó. Vì vậy khi nói đến việc tính toán thời gian thực thi của thuật toán đó chính là thời gian ước lượng, việc này thì thực ra không gây ra vấn đề gì. Bởi vì trong khoa học máy tính thứ được quan tâm nhiều hơn đối với một thuật toán là thời gian thực thi của nó sẽ tăng nhanh như thế nào khi số lượng phần tử đầu vào thay đổi.

Từ đó khái niệm Big-O được ra đời.

Và sau đây là một định nghĩa toán học của Big-O

Cho T(n) và f(n) là hai hàm số dương. Ta viết T(n) = O(f(n)) có nghĩa rằng c . f(n) là cận trên của T(n). Vì vậy tồn tại một hằng số c sao cho T(n) luôn luôn <= c . f(n) với một số n đủ lớn (n >= n0)

Hay nói một cách dễ hiểu hơn:

T(n) = O(f(n)) có nghĩa là T(n) không tăng nhanh hơn f(n).

Lưu ý: Ngoài Big-O, còn có hai khái niệm khác Big Omega(Ω) và Big Thelta(Θ):

Big Omega f(n) = Ω(g(n)) có nghĩa là c . g(n) là cận dưới của f(n), có tồn tại một số n >= n0 sao cho f(n) luôn nhỏ hơn c . g(n)
Big Thelta f(n) = Θ(g(n)) có nghĩa là c1 . g(n) là cận dưới và c2 . g(n) là cận trên của f(n), có tồn tại một số n >= n0 sao cho c1.g(n) <= f(n) <= c2.g(n)