Nguồn bài: Topcoder
Giới thiệu
Trong bài viết này tôi sẽ giới thiệu tới các bạn về chủ đề độ phức tạp tính toán. Trước khi đi vào định nghĩa chính xác của các khái niệm, bài viết sẽ giải thích các lý luận đằng sau những khái niệm đó. Tôi cho rằng việc hiểu các lý luận này có thể còn quan trọng hơn bản thân định nghĩa của các khái niệm.
Tầm quan trọng của những lý luận
Giả sử bạn được phân công viết một chương trình để xử lý một tập dữ liệu gồm nhiều bản ghi mà công ty của bạn đã thu thập. Bạn cài đặt hai thuật toán và kiểm tra chúng bằng một vài tập dữ liệu khác nhau. Thời gian chạy được thống kê trong bảng 1.
| Số lượng bản ghi | 10 | 20 | 50 | 100 | 1000 | 5000 |
| Thuật toán 1 | 0.00s | 0.01s | 0.05s | 0.47s | 23.92s | 47min |
| Thuật toán 2 | 0.05s | 0.05s | 0.06s | 0.11s | 0.78s | 14.22s |
Bảng 1: Thời gian chạy của hai thuật toán 1, 2
Từ bảng 1 ta có thể đánh giá một cách không chính thức rằng thuật toán nào tốt hơn [vì thường là ta có thể ước lượng số lượng bản ghi cần xử lý]. Với một công ty thì kết luận dựa trên việc chạy thử như vậy có thể chấp nhận được. Nhưng với người lập trình, nó sẽ tốt hơn nếu có thể đánh giá thời gian chạy của hai thuật toán trước khi viết code và chạy thử - sau đó chỉ cần cài đặt thuật toán tốt hơn.
Các kỳ thi lập trình cũng đòi hỏi việc đánh giá tương tự: kích cỡ của tập dữ liệu được cho trước trong đề bài. Giả sử ta đã nghĩ ra được một thuật toán. Câu hỏi cần đặt ra trước khi bắt tay vào cài đặt là: thuật toán này có đáng để cài đặt không? Liệu nó có thể chạy trên bộ test lớn nhất trong thời gian cho phép không? Nếu ta có thể nghĩ ra một vài thuật toán khác, nên chọn thuật nào để cài đặt?
Các câu hỏi trên dẫn tới câu hỏi cốt lõi hơn: Làm sao để so sánh hai thuật toán với nhau? Quay trở lại ví dụ 1, ta có thể ước lượng rằng khi số bản ghi vượt quá 1000, thuật toán 2 sẽ chạy nhanh hơn nhiều lần thuật toán 1. Nói cách khác, xét trên tất cả các tập dữ liệu có thể, thuật toán 2 sẽ chạy tốt hơn trong hầu hết các trường hợp.
Có thể kết luận được rằng trong hầu hết các trường hợp - cho trước 2 thuật toán, hoặc là một thuật toán gần như luôn luôn tốt hơn, hoặc là cả hai xấp xỉ tốt như nhau. Như vậy, chúng ta sẽ định nghĩa độ tốt của thuật toán dựa vào đánh giá độ hiệu quả chạy trên toàn bộ tập dữ liệu như trên. Đánh giá này sẽ là ý tưởng chính đằng sau các định nghĩa cụ thể mà chúng ta sẽ đề cập về sau.
Mẹo gộp hai thuật toán
Nếu đối chiếu với hai thuật toán ví dụ 1, không khó để thấy rằng có một thuật toán với thời gian chạy tương tự với chúng trong bảng 2
| Số lượng bản ghi | 10 | 20 | 50 | 100 | 1000 | 5000 |
| Thuật toán 3 | $N$ 0.00s | 0.01s | 0.05s | 0.11s | 0.78s | 14.22s |
Bảng 2: Thời gian chạy của thuật toán 3
Ý tưởng của thuât toán 3: nếu số lượng bản ghi nhỏ thì ta áp dụng thuật toán 1, ngược lại áp dụng thuật toán 2.
Ý tưởng tương tự thường được áp dụng vào thực tế. Một ví dụ là trong các hàm sắp xếp sort[] được cung cấp bởi thư viện của các ngôn ngữ lập trình thường được cài đặt theo thuật toán QuickSort với nhiều cải tiến, ví dụ:
- Nếu số lượng phần tử quá nhỏ, chạy thuật toán sắp xếp chèn InsertSort [vì InsertSort chạy nhanh hơn với tập dữ liệu kích thước nhỏ].
- Nếu vị trí phần tử chốt không tốt, chuyển sang chạy thuật toán sắp xếp trộn MergeSort.
Thế nào là độ hiệu quả của thuật toán?
Giả sử bạn có đoạn mã sau:
for [int i = 0; i 1000$ thì thuật toán đầu tiên chạy nhanh hơn - khi $N$ tăng, khoảng cách về độ hiệu quả giữa hai thuật toán càng trở nên rõ ràng. Trong khi thuật toán đầu tiên có thể giải quyết bài toán với $N = 20 000$ chỉ trong thời gian tính bằng giây, thuật toán thứ hai phải mất tới vài phút trên các máy tính hiện đại.Sự khác biệt như trên sẽ luôn xảy ra nếu một trong hai thuật toán có thời gian chạy tăng tiệm cận nhanh hơn so với thời gian chạy của thuật toán còn lại [nói cách khác, khi $N$ đủ lớn để kết quả phép tính giới hạn lim của tỷ lệ giữa hai đại lượng này bằng 0 hoặc $\infty$. ND: trong bài này tác giả không nói rõ việc so sánh độ phức tạp theo phép tính giới hạn, chỉ cần hiểu khái niệm tiệm cận có nghĩa là kích cỡ đầu vào đủ lớn. Như vậy tiệm cận nhanh hơn có nghĩa là nhanh hơn khi đầu vào đủ lớn]. Bất kể các hằng số nhận giá trị nào, một thuật toán có thời gian chạy tỷ lệ [thuận] với $N^2$ sẽ luôn luôn hiệu quả hơn một thuật toán khác có thời gian chạy tỷ lệ với $N^3$ trong hầu hết các trường hợp của tập đầu vào. Nhận định này chính là ý tưởng chủ đạo để xây dựng định nghĩa chính thức của các khái niệm.
Các khái niệm cơ bản
Gọi $f, g$ là các hàm số dương không giảm trên tập số nguyên dương [lưu ý rằng hàm thời gian chạy thỏa mãn điều kiện này]. Ta nói rằng "$f[N]$ thuộc $O[g[N]]$" [cách đọc: "$f$ thuộc O-lớn của $g$"] nếu tồn tại các giá trị $c$ và $N_0$ thỏa mãn điều kiện sau:
$$ \forall N > N_0; f[N] < c.g[N] $$
Mệnh đề trên có thể diễn dịch như sau: $f[N]$ thuộc $O[g[N]]$ nếu với $c$ nào đó toàn bộ đồ thị của hàm $f$ nằm dưới đồ thị của hàm $c.g$. Chú ý rằng điều này có nghĩa là tốc độ tăng của hàm $f$ không vượt quá độ tăng của hàm $g$. [ND: ký hiệu O-lớn là ký hiệu chỉ tập hợp của các hàm số, vì vậy ở đây quan hệ giữa $f$ và $O[g[N]]$ là [phần tử] thuộc [tập hợp].]
Thay vì viết "$f[N]$ thuộc $O[g[N]]$" ta thường viết là "$f[N]$ = $O[g[N]]$". Chú ý là dấu "=" không có tính đối xứng - viết "$O[g[N]] = f [N]$" là sai và không có ý nghĩa gì, đồng thời mệnh đề "$g[N] = O[f [N]]$" cũng không phải luôn đúng [sẽ được chỉ ra ở phần sau của bài viết].
Định nghĩa trên được biết tới là ký pháp O-lớn và được sử dụng để chỉ ra cận trên của tốc độ tăng của một hàm số.
Xét hàm số $f [N] = 1.5N^2 – 0.5N$ trong ví dụ 2. Ta có thể phát biểu rằng $f [N] = O[N^2]$ [một trường hợp khả dĩ cho các hằng số là $c = 2$ và $N_0 = 0$]. Điều này có nghĩa là hàm $f$ không tăng [tiệm cận] nhanh hơn $N^2$.
Lưu ý rằng thời gian chạy chính xác của hàm $f$ không cho ta câu trả lời cho câu hỏi "Chương trình trên chạy mất bao lâu trên máy tính?". Nhận định quan trọng rút ra từ ví dụ trên là thời gian chạy của hàm $f$ đó là hàm bậc hai. Nếu ta tăng gấp đôi kích cỡ đầu vào, thời gian chạy sẽ tăng xấp xỉ 4 lần thời gian chạy ban đầu, không quan trọng máy tính của ta nhanh như thế nào.
Việc xác định được cận trên $O[N^2]$ của $f[N]$ cũng đưa ta tới cùng nhận định như trên - đảm bảo rằng độ tăng của hàm thời gian chạy tối đa là hàm bậc hai.
Vì vậy, chúng ta sẽ sử dụng ký pháp O-lớn để mô tả độ phức tạp thời gian [và đôi khi là cả bộ nhớ] của các thuật toán. Với thuật toán trong ví dụ 2 ta sẽ nói "Độ phức tạp thời gian của thuật toán này là $O[N^2]$" hoặc ngắn gọn hơn "Thuật toán này là $O[N^2]$".
Theo cách tương tự ta sẽ định nghĩa $ \Omega$ [Omega-lớn] and $ \Theta$ [Theta-lớn].
Ta nói rằng $f [N]= \Omega[g[N]]$ nếu $g[N] = O[f [N]]$, nói cách khác nếu $f$ tăng nhanh hơn hoặc bằng $g$.
Ta nói rằng $f [N] = \Theta[g[N]]$ nếu $f [N] = O[g[N]]$ và $g[N] = O[f [N]]$, nói cách khác nếu cả hai hàm số có độ hiệu quả xấp xỉ bằng nhau.
Dễ dàng nhận thấy là hàm Omega-lớn dùng để chỉ cận dưới và hàm Theta-lớn dùng để chỉ đánh giá chặt [cả hai cận] của một hàm số. Có những đánh giá cận khác tương tự nhưng ít phổ biến hơn.
Một vài mệnh đề sử dụng các ký pháp trên:
- $1.5N^2 -0.5N = O[N^2]$.
- $47N log N = O[N^2]$.
- $N log N + 1 000 047N = \Theta[N log N]$.
- Tất cả các đa thức bậc $k$ là $O[N^k]$.
- Độ phức tạp thời gian của thuật toán trong ví dụ 2 là $ \Theta[N^2]$.
- Nếu một thuật toán thuộc $O[N^2]$, nó cũng thuộc $O[N^5]$.
- Các thuật toán sắp xếp dựa trên phép so sánh đều là $ \Omega[N log N]$.
- Thuật toán sắp xếp trộn MergeSort chạy trên mảng gồm $N$ phần tử thực hiện xấp xỉ $N log N$ phép so sánh. Vì vậy độ phức tạp thời gian của MergeSort là $ \Theta[N log N]$. Nếu mệnh đề trước đó là đúng thì MergeSort tiệm cận thuật toán tối ưu nhất trong các thuật toán sắp xếp dựa trên phép so sánh.
- Thuật toán trong ví dụ 2 sử dụng $ \Theta[N]$ bytes bộ nhớ.
- Hàm số cho biết số răng của một người ở một thời điểm xác định là $O[1]$.
- Một thuật toán quay lui đơn giản giải các bài toán trên bàn cờ vua là $O[1]$ vì cây vị trí mà thuật toán duyệt qua có kích cỡ giới hạn. [Tuy nhiên giá trị hằng số trong $O[1]$ này lại rất lớn]
- Mệnh đề "Độ phức tạp thời gian của thuật toán này tối thiểu là $O[N^2]$" là vô nghĩa. [Diễn dịch: "Giá trị tối thiểu của độ phức tạp thời gian của thuật toán này tối đa là xấp xỉ hàm bậc hai"]. Phát biểu đúng là: "Độ phức tạp thời gian của thuật toán này là $ \Omega[N2]$."
Khi nói về độ phức tạp thời gian/bộ nhớ của một thuật toán, thay vì sử dụng ký pháp Theta-lớn $ \Theta[f [N]]$ ta có thể đơn giản chỉ ra tên của lớp hàm chứa hàm $f$. Ví dụ với $f [N] = \Theta[N]$, ta gọi thuật toán đó là tuyến tính. Một vài ví dụ khác:
- $f [N] = \Theta[log N]$: hàm log
- $f [N] = \Theta[N^2]$: hàm bậc 2
- $f [N] = \Theta[N^3]$: hàm bậc 3
- $f [N] = O[N^k]$ : hàm đa thức
- $f [N] = \Omega[2^N]$: hàm mũ
Với các bài toán trên đồ thị, độ phức tạp $ \Theta$[N + M] được gọi là "tuyến tính theo độ lớn của đồ thị".
Xác định thời gian chạy dựa vào đánh giá cận trên
Với hầu hết các thuật toán thường gặp trong thực tế, giá trị hằng số của $O$ [hoặc $ \Theta$] thường là khá nhỏ. Nếu một thuật toán là $ \Theta[N^2]$, độ phức tạp chính xác là vào khoảng $10N^2$ chứ không phải $10^7N^2$.
Nói cách khác: nếu hằng số là lớn thì thường là các hằng số đó có liên quan tới các đại lượng có sẵn trong đề bài. Trong trường hợp này cách làm thông thường là gán một tên gọi cho hằng số đó và thêm nó vào đánh giá độ phức tạp theo ký pháp, thay vì bỏ qua như ta đã làm với số $1.5$ ở ví dụ 2.
Ví dụ: bài toán yêu cầu đếm số lần xuất hiện của mỗi loại ký tự trong một chuỗi độ dài $N$ ký tự. Thuật toán đơn giản nhất là duyệt cả chuỗi một lần cho mỗi loại ký tự. Kích cỡ bảng chữ cái không thay đổi [ví dụ nhiều nhất là 255 ký tự trong ngôn ngữ C], vì vậy thuật toán là tuyến tính với $N$. Mặc dù vậy, ta nên viết độ phức tạp thời gian là $ \Theta[|S| \times N]$, trong đó $S$ là bảng chữ cái được sử dụng [Lưu ý là có một thuật toán tốt hơn giải bài toán này trong $ \Theta[|S| + N]$.
Trong một kỳ thi trên TopCoder, một thuật toán thực thi 1 000 000 000 phép nhân hiếm khi chạy trong giới hạn thời gian cho phép. Thực tế này cộng với quan sát ở trên và một vài kinh nghiệm với các bài toán trên TopCoder giúp ta tổng kết bảng sau:
| $ \Theta[N]$ | 100 000 000 |
| $ \Theta[N log N]$ | 40 000 000 |
| $ \Theta[N^2]$ | 10 000 |
| $ \Theta[N^3]$ | 500 |
| $ \Theta[N^4]$ | 90 |
| $ \Theta[2^N]$ | 20 |
| $ \Theta[N!]$ | 11 |
Bảng 3: Giá trị $N$ lớn nhất để các thuật toán có độ phức tạp khác nhau chạy trong tối đa 8 giây
Lưu ý khi phân tích độ phức tạp thuật toán
Thông thường khi trình bày một thuật toán, cách tốt nhất để đánh giá độ phức tạp của nó là ký pháp Theta $\Theta$. Tuy nhiên, trong thực tế thường ta chỉ trình bày cận $O-lớn$ vì ký pháp này dễ viết hơn và phổ biến hơn. Nhắc lại rằng $O-lớn$ chỉ mang ý nghĩa cận trên. Thông thường ta tìm cận trên $O-lớn$ nhỏ nhất có thể.
Ví dụ 3
Cho một mảng A đã được sắp xếp. Xác định xem liệu có tồn tại 02 phần tử trong mảng mà cách nhau D đơn vị hay không. Xét lời giải sau
int j = 0; for[int i = 0; i