Bài này mình hướng đến các bạn mới bắt đầu học thuật toán với mục đích giúp các bạn làm quen với một số khái niệm như $O(.), o(.), \Omega(.), \Theta(.)$. Mình đã có một bài riêng định nghĩa các khái niệm này một cách hình thức. Bài này mình bổ sung các định nghĩa đó bằng những giải thích trực quan hơn.
Khi phân tích một thuật toán, ta thường quan tâm đến bộ nhớ và thời gian tính toán. Khi chúng ta đã thành thạo phân tích một trong hai tài nguyên thì phân tích tài nguyên còn lại không phải quá khó khăn. Do đó, bài viết này mình sẽ chỉ tập trung nói về phân tích thời gian tính toán của một thuật toán.
Phân tích một thuật toán về cơ bản là đếm số thao tác cơ bản mà thuật toán đó thực hiện. Định nghĩa chính xác thế nào là một thao tác cơ bản là việc không tầm thường. Tuy nhiên, để đơn giản, ta tạm coi các thao tác cơ bản ở đây là: cộng, trừ, nhân, chia, so sánh và mỗi thao tác cơ bản này mất 1 đơn vị thời gian. Do đó, đôi khi ta cũng coi số thao tác cơ bản như là một ước lượng thô của thời gian tính toán. Mình nói ước lượng thô là vì thời gian thực phụ thuộc rất nhiều vào máy tính (hay mô hình tính toán) mà ta sử dụng. Cùng 1 triệu phép nhân số 32 bít nhưng thời gian tính toán của phần cứng khác nhau có thể khác nhau. Tuy nhiên, ta vẫn chấp nhận cách ước lượng thô này vì nó sẽ làm phép phân tích thuật toán đơn giản hơn, loại bỏ sự phụ thuộc phần cứng ra khỏi phép phân tích.
Tại sao dùng Big-O?
Cách giải thích tốt nhất có lẽ là minh họa thông qua ví dụ.
Ví dụ 1: phân tích thời gian của thuật toán sau:
$s \leftarrow 0$
for $i \leftarrow 1$ to $n$
$s \leftarrow s + A[i]$
return $s$
Thuật toán SumOfArray nhận đầu vào là một mảng $A[1,\ldots, n]$ với $n$ phần tử và trả lại tổng $A[1] + A[2] + \ldots + A[n]$.
Ta sẽ đếm số phép cộng của thuật toán trước. Mỗi lần lặp, thuật toán SumOfArray thực hiện một phép cộng để cập nhật $s$. Do ta có $n$ vòng lặp, thuật toán thực hiện $n$ phép cộng để tìm $s$.
Thuật toán SumOfArray chỉ thực hiện $n$ phép cộng? Không hẳn thế. Nếu bạn lập trình bằng ngôn ngữ C chẳng hạn, thì mỗi lần thực hiện vòng lặp for, bạn phải tăng biến đếm $i$ lên $1$. Do đó, ta phải tính cả số phép cộng thực hiện trên biến $i$ mà không phải chỉ với biến $s$. Số phép cộng tăng lên $2n$.
Nếu coi mỗi phép cộng mất 1 đơn vị thời gian thì thời gian của thuật toán SumOfArray có phải là $2n$ đơn vị thời gian? Cũng không hẳn như vậy. Sau mỗi lần lặp, thuật toán còn phải so sánh $i$ với $n$ để kiểm tra điều kiện kết thúc vòng lặp. Do đó, thuật toán sử dụng thêm $n$ phép so sánh. Vẫn chưa hết, thuật toán còn sử dụng $n$ phép gán với biến $s$ và $n$ phép gán với biến $i$. Tóm lại, thuật toán sử dụng khoảng $5n$ phép toán cơ bản nếu bạn thực thi bằng $C$.
Nếu bạn thực thi đoạn code trên bằng ngôn ngữ khác $C$, số lượng phép toán cơ bản có thể nhiều hơn như vậy. Tưởng tượng với đoạn code rất đơn giản trên mà thực hiện đếm chính xác số lượng phép toán cơ bản đã không tầm thường thì với các đoạn chương trình phức tạp hơn thì ta làm thế nào? Big-O $O(.)$ sẽ giúp bạn đếm đơn giản hơn!
Thay vì đếm chính xác, $O(.)$ cho phép ta đếm tương đối số thao tác cơ bản. Theo phân tích ở trên, dù ta thực thi thuật toán SumOfArray bằng bất kì ngôn ngữ nào thì số lượng phép toán cơ bản đều không quá $C\cdot n$ với một hằng số $C$ nào đó. Hằng số $C$ có thể là 5 hoặc 10 hoặc 4. Ta gọi nó là hằng số là vì giá trị của nó không phụ thuộc vào $n$. Theo định nghĩa hình thức của big-O, ta có thể nói:
Thuật toán SumOfArray có thời gian $O(n)$.
Tóm lại, khi ta nói một thuật toán có độ phức tạp $O(f(n))$, ta muốn nói số lượng phép toán cơ bản mà thuật toán sử dụng không quá $C \cdot f(n)$ với một hằng số $C$ nào đó khi $n$ đủ lớn, bất chấp ngôn ngữ lập trình sử dụng. Như vậy, khi dùng $O(.)$ để phân tích thuật toán, ta có thể loại bỏ sự phụ thuộc vào ngôn ngữ lập trình (hay thực thi mức thấp) của thuật toán.
Ví dụ 2: Phân tích thuật toán.
for $i \leftarrow 1$ to $n-1$
for $j \leftarrow i+1$ to $n$
if $A[i] $ > $A[j]$
$tmp \leftarrow A[i]$
$A[i] \leftarrow A[j]$
$A[j] \leftarrow tmp$
return $A[1,2,\ldots, n]$
Có lẽ bạn đọc cũng nhận ra thuật toán BubbleSort thực hiện sắp xếp một mảng đầu vào theo chiều tăng dần. Để phân tích thuật toán này, ta chỉ cần đếm số phép so sánh các phần tử của mảng $A[1,\ldots, n] $ (số lần kiểm tra điều kiện của câu lệnh if). Tại sao? Ngoại trừ khi $n = 1$, mỗi khi ta thực hiện thao tác bất kì (gán, đổi chỗ, v.v), ta đều thực hiện một phép so sánh. Do đó, chỉ cần đếm số phép so sánh và sử dụng khái niệm $O(.)$ là ta coi như đã xong.
Do mỗi lần lặp ta sử dụng một phép so sánh, thay vì đếm số phép so sánh, ta đếm số lần lặp. Với mỗi $i$ cố định, vòng lặp trong cùng có $n-(i+1) + 1 = n-i$ lần lặp. Do đó, tổng số lần lặp là:
$\sum_{i=1}^{n-1} n-i = \sum_{j=1}^{n-1} j = n (n-1)/2 = n^2/2 - n/2 \qquad (1)$
Như vậy, độ phức tạp của thuật toán BubbleSort là $O(n^2/2-n/2)$.
Theo định nghĩa của $O(.)$, ta có thể loại bỏ hằng nhân tử hằng số trong biểu thức. Do đó, ta có thể viết $O(n^2/2-n/2) = O(n^2-n) = O(n^2)$. Tổng kết lại, ta có:
Từ phân tích ví dụ 2, ta có thể thấy rằng kí hiệu $O(.)$ cho phép chúng ta biểu diễn thời gian tính toán bằng các biểu thức đơn giản hơn. Không chỉ có vậy, $O(.)$ còn cho phép chúng ta phát triển các công cụ phân tích mạnh hơn, tổng quát hơn nhưng lại dễ hiểu hơn. Để minh họa điểm này, ta xét ví dụ sau.
Ví dụ 3: Phân tích thuật toán.
if $n$ > $1$
$m \leftarrow \lfloor n/2\rfloor$
MergeSort($A[1,2,\ldots, m]$)
MergeSort($A[m+1,2,\ldots, n]$)
Merge($A[1,2,\ldots, n],m$)
$i \leftarrow 1; j \leftarrow m+1$
for $k \leftarrow 1$ to $n$
if $j$ > $ n$
$B[k] \leftarrow A[i]; i \leftarrow i + 1$
else if $i$ > $m$
$B[k] \leftarrow A[j]; j \leftarrow j + 1$
else if $A[i]$ > $A[j] $
$B[k] \leftarrow A[i]; i \leftarrow i + 1$
else
$B[k] \leftarrow A[j]; j \leftarrow j + 1$
for $k \leftarrow 1$ to $n$
$A[k] \leftarrow B[k]$
Không khó để nhận ra thuật toán MergeSort thực hiện sắp xếp một mảng theo chiều tăng dần, sử dụng phương pháp chia để trị. Phương pháp thường dùng để phân tích thuật toán kiểu chia để trị là giải hệ thức truy hồi. Ta gọi $T(n)$ là độ phức tạp của thuật toán MergeSort khi mảng đầu vào có $n$ phần tử. Độ phức tạp của hai thủ tục gọi đệ quy lần lượt là $T(\lfloor n/2 \rfloor)$ và $T(\lceil n/2 \rceil)$. Phân còn lại của phép phân tích là tính độ phức tạp của thủ tục Merge.
Nếu bạn đếm chính xác số thao tác cơ bản của thủ tục Merge là một điều không hề dễ dàng vì có các lệnh điều kiện if-else. Tuy nhiên, sử dụng $O(.)$, ta có thể khẳng định số thao tác cơ bản là $O(n)$ vì ta chỉ lặp $n$ lần và mỗi lần lặp ta thực hiện $O(1)$ phép tính cơ bản. Do đó, ta có:
$T(n) = T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + O(n) \qquad (2)$
Recent Comments