[Thuật toán] Độ Phức Tạp Không Hề Phức Tạp

Bài viết được sự cho phép của tác giả Trần Thiện Khiêm

Trong loạt bài này mình sẽ giới thiệu về thuật toán và một số thuật toán cơ bản hay được sử dụng + giải thích cho các bạn.

THUẬT TOÁN LÀ GÌ?

Nhưng đầu tiên hết hãy tìm hiểu xem thuật toán là gì? Nói đơn giản thuật toán là:

“Tập hợp các bước để xử lí một vấn đề (loại vấn đề) nào đó.”

Ví dụ, để tính tổng các số tự nhiên từ 1 – N, thì chúng ta làm các bước sau (1)

– Gán tổng = 0

– Cộng tổng với 1

– Cộng tổng với 2

…

– Cộng tổng với n

– Ta được kết quả tổng là kết quả.

Hay nói một cách khác (2)

– Gán Tổng = 0

– Lần lượt với tất cả giá trị i trong đoạn 1 tới N, cộng i vào tổng

Hoặc có 1 cách khác (3)

– Tính tổng = N * (N + 1) / 2.

Như vậy các bước giải vấn đề, người ta gọi là thuật toán. Vậy bất cứ khi nào các bạn viết code, thì đó chính là thuật toán. Nên nếu có ai đó nói với bạn rằng, học thuật toán làm gì sau này đi làm không có dùng thuật toán, thế thì hãy hỏi lại: “không xài thuật toán thì bạn code cái gì vậy?”. Không có vụ không có thuật toán mà có code nhé, chỉ có thuật toán ngon hay dở thôi.

Tất nhiên đối với một vấn đề, có thể có nhiều cách giải quyết khác nhau, có cách giải quyết nhanh chóng, có cách giải chậm, có cách giải đơn giản, có cách giải phức tạp, đó là lý do học thuật toán. Đó là lí do tại sao người ta có senior dev, có junior. Đó cũng là lí do tại sao mấy công ty lớn người ta lại hỏi về thuật toán. Học thuật toán, chúng ta học gì:

– Học tư duy thuật toán để khi có một vấn đề mới chúng ta biết cách tiếp cận, biết cách đánh giá lời giải chúng ta đưa ra.

– Học các thuật toán phổ biến để khi gặp trường hợp tương tự chúng ta biết cách sử dụng mà không phải tốn thời gian nghĩ ra các lời giải khác. Thường thường các thuật toán này đã đươc viết lại dạng thư viện, nên chúng ta có thể dựa vào đó để tìm ra thư viện tương ứng để xài, vừa đạt hiệu quả cao nhất, mà không phải tốn công giải lại (nói nôm na là copy và paste ở 1 đẳng cấp khác).

ĐÁNH GIÁ THUẬT TOÁN

Thường chúng ta có thể dùng phương pháp đo thời gian chạy (benchmark) để đánh giá xem thuật toán đưa ra có hiệu quả không. Đây là cách chính xác nhất. Tuy nhiên, cách này có một nhược điểm là chúng ta phải code xong thuật toán đó, và nó hoàn toàn phụ thuộc vào kích thước mẫu của dữ liệu đưa vào. Cách này có thể các bạn sẽ thấy khi các bạn submit bài leetcode, nếu timeout thì chắn tỏ thuật toán của toán của bạn quá cùi

Có 1 cách đánh giá khác đơn giản hơn trước khi bạn code đó là đánh giá dựa vào độ phức tạp thời gian (time complexity). Chúng ta có thể đánh giá ngay thuật toán trước khi code, để xem thuật toán có khả thi hay không.

độ phức tạp thời gian

VẬY ĐỘ PHỨC TẠP THỜI GIAN LÀ GÌ?

Nôm na độ phức tạp thời gian của thuật toán là ước lượng thời gian thực thi của thuật toán đó theo kích thước dữ liệu đầu vào. Chính vì có sự phụ thuộc này nên độ phức tạp thuật toán được biểu diễn dưới dạng hàm số O(1), O(N), O(N2), nghe thật đau đầu và khó hiểu…

Vậy mình xin có 1 số ví dụ như sau:

Với bài toán nêu trên, tính tổng của các số tự nhiên từ 1 .. N, chúng ta có 3 cách, tuy nhiên cách đầu tiên khó mà tổng quát hoá được, nên chúng ta sẽ tập trung vào cách (2), và cách (3).

Với cách số (2), chúng ta phải tính N phép tính cộng, giả sử một phép tính tốn 1ms (giả sử máy tính cùi bắp nha), thì ta có kết quả sau:

N = 1, thời gian là 1ms.

N = 2, thời tian là 2ms,

N = 10, thời gian là 10ms. (vì phải cộng 10 lần)

Ta thấy thời gian tỉ lệ thuận với N, do đó ta gọi thuật toán này có độ phức tạp tuyến tính (linear complexity) hay O(N), nếu N tăng lên 10 lần, thì thời gian của thuật toán sẽ tăng thêm 10 lần, nếu N tăng lên 1000 lần, thời gian sẽ tăng lên 1000 lần.

Đối với cách (3), cho dù với N bằng bao nhiêu đi nữa, thì chúng ta chỉ cần 1 phép tính toán như nhau để tìm ra kết quả. Vậy thời gian không hề phụ thuộc vào dữ liệu đầu vào. Người ta gọi đây là độ phức tạp hằng số (constant time), hay O(1). Ví dụ, nếu thời gian để thực hiện công thức tên tốn 3ms, thì với bất cứ N nào, cũng sẽ tốn 3ms (với lí tưởng là thời gian thực thi của máy tính như nhau).

MỘT SỐ VÍ DỤ KHÁC

Thuật toán tìm kiếm tuần tự:

Giả sử chúng ta cần tìm một phần tử trong danh sách cho sẵn, thì chúng ta phải lần lượt kiểm tra từng phần tử cho đến khi tìm thấy phần tử cần tìm, đây gọi là thuật toán tìm kiếm tuần tự.

Ứng dụng:

String.indexOf(), Collection.indexOf(): xác định vị trí 1 ký tự trong chuỗi hoặc một phần tử trong Collection. Những thứ các bạn xài hằng ngày.

SELECT id FROM TABLE WHERE AGE=30; tìm một thành phần trong một bảng cơ sở dữ liệu mà cột chưa được đánh index.

Độ phức tạp: tuyến tính hay O(N).

Các bạn sẽ thắc mắc, là chúng ta có cần phải chạy hết N phần tử đâu, vì sao vẫn gọi là O(N), nếu phần tử cần tìm của mình nằm ở vị trí số 1, hoặc số 2, thì mình sẽ tìm ra ngay, và rõ ràng không cần chạy hết N bước.

Giải thích: giả sử phân bố của tất cả các phần tử là như nhau, thì với N phần tử, số bước tính trung bình của thuật toán này là xấp xỉ N/2 bước. Bây giờ, mình tăng N lên 10 lần, thì số bước trung bình của thuật toán này là xấp xỉ 10N/2. (10N/2) / (N/2) thì vẫn là tăng lên 10 lần, đảm bảo định nghĩa của O(N).

Rõ ràng, với độ phức tạp như thế này, các bạn sẽ cần phải cân nhắc sử dụng các thuật toán tìm kiếm tốt hơn nếu bộ dữ liệu của mình đủ lớn, hoặc nếu thuật toán này được gọi trong một vòng lặp khác. Vậy có những thuật toán tìm kiếm nào khác…

Nếu không biết thì xem độ phức tạp này ở đâu?

Trường hợp của các hàm có sẵn trong thư viện, chúng ta có thể tra document của ngôn ngữ đó để tìm ra độ phức tạp, hoặc google…

Với SQL chúng ta có thể sử dụng câu lệnh EXPLAIN

Nếu còn không tìm ra thì lo học đi ạ…

(còn tiếp…)

Bài viết gốc được đăng tải tại fanpage Khiem Tran – Programmer

Hiểu thêm về thuật toán, nếu bạn muốn:

Đừng bỏ lỡ việc làm IT lương cao trên TopDev nhé!