Độ phức tạp thuật toán

 Độ phức tạp thuật toán

Với nhiều lập trình viên, học lập trình thường gói gọn trong hai việc, học thuộc cú pháp của ngôn ngữ và làm theo một vài bài tập hướng dẫn nào đó. Và với rất nhiều người thì chỉ như vậy là đủ. Tôi cũng đã có lúc như các bạn, học lập trình, rồi ra đi làm, ngồi gõ code kiếm cơm. Cho đến một ngày đẹp trời, tôi được hướng dẫn về một thứ mà tôi cứ tưởng tôi đã biết.

Vâng, hôm nay tôi muốn trình bày một chút về độ phức tạp của thuật toán, hay còn gọi là ký hiệu O lớn. Vậy ta nên định nghĩa thế nào về ký hiệu O lớn? Theo tôi ta có thể định nghĩa như sau:

Ký hiệu O lớn là thước đo tương đối về độ phức tạp của một thuật toán nhất định.

Và tôi muốn nhấn mạnh đến 3 điểm.

Thứ nhất là sự tương đối. Bởi vì sao? Đơn giản là ta đều biết là chúng ta chỉ nên so sánh hai vật tương xứng, như so sánh táo với táo, cam với cam, chứ không nên so sánh cam với táo. Nhưng trong thế giới của lập trình viên, đôi lúc chúng ta vẫn cần có một sự so sánh tương đối nào đó để có thể đi đến một kết luận nhất định (dựa trên thời gian hoặc bộ nhớ trong).

Thứ hai là sự đo lường, ký hiệu O lớn giúp chúng ta đơn giản hóa thuật toán phức tạp thành một biến số. Và biến số đó được lựa ra dựa trên một số giả thuyết và quan sát nhất định. Lấy ví dụ, hầu hết các thuật toán sắp xếp được đo đạc dựa trên phép so sánh của 2 phần tử. Ở đây, giả thuyết của chúng ta là phép so sánh là một phép tính tốn kém. Nhưng điều gì sẽ xảy ra nếu phép hoán đổi tốn kém hơn phép so sánh? Khi đó mọi chuyện sẽ thay đổi hoàn toàn.

Cuối cùng chính là độ phức tạp. Nếu so sánh 10’000 số tốn của bạn một giây, thì so sánh 1’000’000 số sẽ tốn của bạn bao lâu? Và ở đây độ phức tạp là một thước đo tương đối dựa trên một thứ khác, thời gian.

Số học

Đầu tiên ta hãy lấy số học làm ví dụ. Hãy chọn hai số tương đối lớn, và ở trường họ dạy bạn làm những gì?

• Cộng
• Trừ
• Nhân
• Chia

Mỗi phép toán là một phép tính hoặc là một vấn đề. Phương thức giải mỗi phép toán này có thể gọi là một thuật toán.

Phép cộng là đơn giản nhất, bạn sắp cho hai số thẳng hàng với nhau về tay phải rồi cộng từng cột. Bạn viết số lẻ và “nhớ 1″ lên cột bên trái liền kề. Giả sử như phép cộng từng cột này tốn kém nhất, thì bạn có thể kết luận rằng cặp số của bạn có bao nhiêu chữ số thì bạn sẽ cần làm tối đa bằng đó phép cộng (và cố thể là thêm 1 lần “nhớ 1″ nữa). Nếu ta cộng hai số có 100 chữ số thì ta sẽ cần khoảng 100 phép cộng, 10’000 chữ số thì cần 10’000 phép cộng, v.v.

Bạn đã mường tượng ra được rồi phải không? Độ phức tạp có liên quan trực tiếp đến số chữ số của số lớn hơn. Ta gọi kiểu phức tạp này là O(n) hay còn gọi là độ phức tạp tịnh tiến (dân gian còn gọi là cấp số cộng :3). Phép trừ cũng tương tự như phép cộng, sự khác biệt có chăng là bạn cần “mượn 1″ thay vì “nhớ 1″.

Phép nhân lại là một câu chuyện khác. Bạn sắp hai số cho thẳng hàng xong, bạn nhân chữ số tận cùng bên phải của thừa số hàng dưới với từng chữ số của thừa số ở hàng trên, rồi thêm làm phép cộng cho mỗi lần bạn cần “nhớ”. Bạn lặp lại như vậy với tất cả các chữ số của thừa số dưới. Cuối cùng bạn sẽ phải cộng các dòng nhân lại với nhau để ra được kết quả cuối cùng. Và nôm na là bạn sẽ cần phải làm x nhân y lần phép nhân với x và y là số chữ số của hai thừa số ban đầu. Nếu hai chữ số này có 100 chữ số, bạn sẽ phải làm 10’000 phép nhân và 200 phép cộng theo hàng cột.

Nếu hai thừa số có số chữ số bằng nhau là n, thì độ phức tạp của phép tính tỉ lệ thuận với n^2, ta gọi độ phức tạp này là O(n^2) (cấp số nhân). Tất nhiên ta có thể viết chi tiết hơn là n^2 + 2n, nhưng ta thực ra chỉ cần quan tâm tới n^2 là đủ, vì với n càng lớn thì 2n << n^2. Ở đây ta lại có thêm một khái niệm quan trọng nữa, đó là ta chỉ cần quan tâm tới phần nặng hơn trong độ phức tạp.

Có bạn sẽ nói rằng ta đang đề cập đến trường hợp xấu nhất, đó là khi hai số có số chữ số bằng nhau và bằng n. Còn trường hợp đó là 2 số khác nhau m và n thì sao? Xin thưa với các bạn là ký hiệu O lớn luôn xem xét khả năng xấu nhất của thuật toán và n^2 là trường hợp đặc biệt nhất của n*m.

Cuốn danh bạ điện thoại

Ví dụ hay nhất tiếp theo mà tôi nghĩ đến là cuốn danh bạ điện thoại. Thứ mà chúng ta quan tâm đến là một danh sách dài (rất dài đối với con người) gồm có tên họ, số điện thoại và địa chỉ.

Nếu bạn cần cho máy tính tìm tên 1 người nào đó trong một danh sách khoảng 1’000’000 dòng thì bạn sẽ làm thế nào? Con người là một động vật thông minh và tôi dám chắc là bạn sẽ dự đoán cái tên bạn cần tìm ở một khoảng nào đó và bắt đầu tìm từ đấy, nhưng máy tính thì không có khả năng đó.

Các làm đơn giản nhất là bắt đầu từ chính giữa và so sánh với tên bạn cần tìm. Trừ trường hợp vô cùng may mắn là bạn tìm trúng ngay lập tức, thì cái tên đó sẽ nằm trước hoặc sau vị trí giữa này. Nếu nó ở phía trước thì ta chia đôi phần từ đầu đến giữa hoặc ngược lại nếu nó ở phía sau. Ta cứ làm như vậy cho đến bao giờ tìm được thì thôi. Cách tìm này được gọi là cách tìm nhị phân và được sử dụng hàng ngày trong lập trình mà có khi bạn không biết.

Vậy nếu bạn cần tìm 1 người trong quyển danh bạ 1 triệu dòng thì bạn chỉ cần “chia đôi-tìm” tối đa 20 lần. Khi so sánh các thuật toán tìm, ta coi số phần tử ban đầu là n.

Với một danh sách có 3 dòng, bạn cần làm tối đa 2 phép tìm
Bảy dòng bạn cần 3 phép tìm
15 dòng bạn cần 4 phép tìm
…
1’000’000 dòng bạn cần 20 phép tìm
Quá tốt phải không các bạn?

Theo cách gọi của ký hiệu O lớn thì đây là độ phức tạp O(log n) hay độ phức tạp lô ga rít. Phép lô ga rít này có thể là log_e, log10, log2 hoặc là log khác. Chuyện đó không quan trọng chừng nào độ phức tạp vẫn là O(log n) cũng giống như O(2n^2) hay O(100n^2) thì cũng vẫn được coi là O(n^2).

Ở đây ta thấy có thể có 3 khả năng với độ phức tạp lô ga rít:

Trường hợp tốt nhất là ta tìm thấy ngay ở phép tìm đầu tiên. Độ phức tạp ở đây là O(1) hay còn gọi là độ phức tạp hằng số.
Trường hợp dự tính: chính là O(log n) như đã ví dụ ở trên.
Trường hợp xấu nhất: cũng là O(log n)
Thường thì chúng ta không quan tâm đến trường hợp tốt nhất (vì quá hiếm), mà ta chỉ quan tâm đến trường hợp dự tính và trường hợp xấu nhất. Tùy từng thuật toán mà một trong hai trường hợp sẽ quan trọng hơn (và thường là hai trường hợp này có độ phức tạp khác nhau).

Quay trở lại câu truyện danh bạ điện thoại.

Nếu bạn có số điện thoại và muốn tìm tên người thì sao? Cảnh sát có một danh sách như vậy nhưng nó được cất giữ kỹ. Nhưng thế không có nghĩa là bạn không thể tìm được nếu bạn muốn.

Bạn bắt đầu với cái tên đầu tiên và đi dần xuống danh sách cho đến khi tìm thấy. Bạn phải làm vậy bởi vì danh sách này không được sắp xếp theo trật tự của các số điện thoại.

Vì vậy nếu bạn muốn tìm một cái tên:
Trường hợp tốt nhất vẫn là 1 bước, O(1)
Trường hợp bình quân là 500’000 bước, O(n) (thực ra là O(n/2))
Trường hợp xấu nhất là 1’000’000, O(n)

Người bán hàng rong

Đây là một bài toán kinh điển của công nghệ máy tính và đáng được đề cập đến. Đề bài là bạn có N thị trấn, mỗi thị trấn này được nối tới 1 hoặc nhiều thị trấn khác bởi một con đường có chiều dài nhất định. Vấn đề của người bán hàng là làm sao có thể đi hết tất cả các thị trấn với con đường ngắn nhất.

Nghe có vẻ đơn giản nhỉ? Bạn hãy cẩn trọng.

Nếu bạn có 3 thị trấn A B C với đường nỗi giữa mỗi cặp thì bạn có thể đi bằng 3 cách khác nhau mà không bị lặp.
Nếu bạn có 4 thị trấn, thì sẽ là 12 cách. 5 thị trấn là 60, 6 thị trấn là 360…
Trong toán học ta gọi đây là phép giai thừa. Và đối với ký hiệu O lớn thì đây là độ phức tạp O(n!) hay độ phức tạp tổ hợp. Và khi bạn lên tới 200 thị trấn thì sẽ chẳng có đủ thời gian trên đời này để tính với máy vi tính thông thường.

Vài điều cho các bạn suy ngẫm

Bạn có 2 mảng dữ liệu với n và m phần tử, tùy thuộc vào đề bài bạn cần giải mà thuật toán của bạn sẽ có độ phức tạp O(n+m) hay O(n*m) hay thậm chí O(n^m). Và nếu chẳng may bạn giải với thuật toán O(n^m) thì bạn tiêu chắc rồi :3. Không phải lúc nào ta cũng có thể có được một thuật toán có độ phức tạp O(1) hay O(n), nhưng bạn luôn phải nhớ rằng O(n^2), O(n*m) là những độ phức tạp rất cao, và thường là có thể tối ưu hóa tốt hơn.

Trở lại bài toán tìm tên dựa theo số điện thoại, nếu bạn cần phải tìm nhiều lần, thì cách giải hay nhất là bạn sắp xếp lại danh sách đó theo thứ tự của số điện thoại với độ phức tạp O(n*log n) rồi sau đó tìm nhị phân O(log n). Vì vậy bạn cũng cần tính đến mật độ sử dụng của thuật toán để đưa ra lựa chọn đúng đắn.

Cuối cùng tôi xin nói qua về tính khả thi. Tất cả những thuật toán O(n) hay O(n^2) đều là những thuật toán khả thi, có thể giải quyết được trong một khoảng thời gian hợp lý. Có những bài toán không khả thi như bài toán người bán hàng rong với độ phức tạp O(n!). Và vì thế mà có một số thứ được sử dụng dựa vào tính chất này. Mã hóa public key là một ví dụ điển hình. Việc tìm ra 2 thừa số nguyên tố của một số cực kỳ lớn là một việc rất tốn kém về công suất tính toán, nếu không thì chúng ta đã không thể sử dụng cơ chế mã hóa này.

Lời kết

Có thể sau khi đọc xong bạn cũng vẫn chưa thấy được mối liên quan giữa độ phức tạp và công việc lập trình của bạn. Không sao cả, vì có thể công việc của bạn không cần phải xử lý nhiều dữ liệu. Nhưng nếu một ngày đẹp trời bạn tự hỏi tại sao game Starcraft (1998) lại hạn chế tối đa 1500 đơn vị trong một trận thì bạn hãy nghĩ về bài viết này và có lẽ bạn sẽ nhận ra nguyên nhân.

Và tôi cũng muốn dành một lời khuyên cho các bạn lập trình viên trẻ. Lập trình không chỉ đơn giản là “Hello World!” mà nó còn là cả một nghệ thuật. Trong thời đại người người Java, nhà nhà dotNet (tôi gọi đấy là những ngôn ngữ lập trình lười nhác) thì khi bạn ứng tuyển vào một công ty phần mềm thực sự, hiểu biết thực thụ của bạn về thuật toán sẽ giúp bạn nổi bật lên so với những ứng viên khác. Biết đâu một ngày đẹp trời nào đấy bạn sẽ được mời làm việc cho Google nhỉ?

Dịch và biên tập lại từ một câu trả lời rất hay trên StackOverflow.

Các bạn có thể tra cứu độ phức tạp cho các thuật toán thường dùng ở đây.