Big-O là gì?

Bạn cần code hiệu quả nhưng làm thế nào để làm được việc đó? Câu trả lời chính là Big-O. Ký hiệu Big-O là một công cụ tiện ích giúp bạn tính toán code thực sự hiệu quả như thế nào.

Big-O là gì?

Big-O cung cấp cho bạn cách tính toán thời gian chạy code. Bạn có thể tính toán được con số đó nhưng với phương pháp này, bạn dễ dàng phát hiện những sự khác biệt nhỏ. Ví dụ, thời gian chạy giữa 20 và 50 dòng code chênh lệch không đáng kể nên không ảnh hưởng nhiều tới lập trình. Tuy nhiên, trong một chương trình lớn, những điểm kém hiệu quả đó có thể tăng lên.

Ký hiệu Big-O đếm số bước của thuật toán cần thực hiện để đánh giá hiệu quả của nó. Tiếp cận code theo phương pháp này có thể cực kỳ hiệu quả nếu bạn cần tinh chỉnh code. Big-O sẽ giúp bạn đo các thuật toán khác nhau qua những bước cần thiết để chạy và so sánh khách quan hiệu quả của thuật toán.

Làm thế nào để tính toán ký hiệu Big-O?

Lấy ví dụ hai công thức tính số lượng tất trong ngăn kéo. Mỗi hàm sẽ tính số lượng đôi tất và trả về số lượng từng chiếc tất. Code này được viết bởi Python nhưng điều đó không ảnh hưởng tới cách chúng ta đếm số lượng các bước.

Thuật toán 1:

def sockCounter(numberOfPairs):
individualSocks = 0
for x in range(numberOfPairs):
individualSocks = individualSocks + 2
return individualSocks

Thuật toán 2:

def sockCounter(numberOfPairs):
return numberOfPairs * 2

Đây là một ví dụ ngớ ngẩn và bạn dễ dàng biết được thuật toán nào hiệu quả hơn. Thế nhưng, thực tế, chúng ta hãy xem xét từng bước.

Thuật toán 1 có nhiều bước:

1. Nó gán giá trị 0 cho biến individualSocks.
2. Nó gán giá trị 0 cho biến i.
3. Nó so sánh giá trị i cho numberOfPairs.
4. Nó thêm 2 vào individualSocks.
5. Nó gán các giá trị gia tăng cho individualSocks.
6. Nó tăng dần từng thứ một.
7. Sau đó, nó lặp lại các bước từ 3 tới 6 với số lần tương tự như (indiviualSocks - 1).

Số bước phải hoàn thành thuật toán một có thể được biểu thị bằng:

4n + 2

Có 4 bước cần phải hoàn thành n lần. Trong trường hợp này, n sẽ bằng giá trị của numberOfPairs. Ngoài ra cũng có hai bước cần cần được hoàn thành một lần. Trong khi đó, thuật toán 2 chỉ có 1 bước. Giá trị của numberOfPairs được nhân với 2 và kết quả là:

1

Giờ chúng ta dễ dàng thấy thuật toán 2 hiệu quả hơn một chút.

Phân tích Big-O

Nhìn chung, khi bạn quan tâm tới ký hiệu Big-O của một thuật toán, bạn càng quan tâm hơn tới hiệu quả tổng thể và ít quan tâm hơn tới phân tích chi tiết về số bước. Để đơn giản hóa ký hiệu này, bài viết sẽ xét tới hiệu quả.

Ở ví dụ trên, thuật toán 2 sẽ được thể hiện như 1:

O(1)

Nhưng thuật toán 1 sẽ được đơn giản hóa thành:

O(n)

Điều đó cho chúng ta thấy hiệu quả của thuật toán 1 gắn liền với giá trị n. Con số này càng lớn, các bước thuật toán cần hoàn thành càng nhiều.

Code tuyến tính

Do giá trị n ở đây chưa xác định nên tốt hơn, chúng ta nên xét tới cách giá trị n ảnh hưởng tới số lượng code cần chạy như thế nào. Ở thuật toán 1, mối liên hệ này là tuyến tính. Nếu vẽ biểu đồ số bước so với giá trị n, đó sẽ là một đường thẳng đi lên.

Code bậc hai

Không phải tất cả mối quan hệ đều đơn giản như ví dụ tuyến tính này. Hãy tưởng tượng, bạn có một mảng 2D và muốn tìm giá trị trong mảng đó. Bạn có thể tạo một thuật toán như sau:

def searchForValue(targetValue, arraySearched):
foundTarget = False
for x in arraySearched:
for y in x:
if(y == targetValue):
foundTarget = True
return foundTarget

Ở ví dụ này, số bước phụ thuộc vào số các mảng trong arraySearched và số giá trị trong mỗi mảng. Vì thế, đơn giản hóa số bước sẽ là n * n hoặc n².

Mối quan hệ trên là toàn phương, nghĩa là số bước trong thuật toán phát triển theo cấp số nhân n. Trong ký hiệu Big-O, bạn sẽ viết nó như sau:

O(n²)

Code Logarit

Dù còn nhiều mối quan hệ khác, mối quan hệ cuối cùng chúng ta cần xem xét là logarit. Nhắc lại một chút, logarit của một số là giá trị lũy thừa cần thiết để đạt được một số dựa trên cơ số. Ví dụ:

log 2 (8) = 3

Logarit bằng 3 bởi nếu cơ số là 2, chúng ta cần giá trị lũy thừa của 3 để có số 8.

Vì thế, mối quan hệ của hàm logarit đối lập với hàm cấp số nhân. Khi n tăng, số bước cần chạy thuật toán sẽ ít hơn.

Thoạt nhìn, điều này có vẻ phản trực quan. Làm thế nào các bước của một thuật toán có thể tăng chậm hơn n? Một ví dụ hay là tìm kiếm thập nhị phân. Hãy xét thuật toán tìm kiếm một số trong một mảng của các giá trị duy nhất.

• Bắt đầu bằng một mảng để tìm nó theo thứ tự từ nhỏ nhất tới lớn nhất.
• Tiếp theo, kiểm tra giá trị ở giữa dãy.
• Nếu số đó cao hơn, chúng ta sẽ loại bỏ các số thấp hơn trong kết quả tìm kiếm và nếu số đó thấp hơn, chúng ta sẽ loại bỏ các số cao hơn.
• Giờ hãy nhìn vào số ở giữa các số còn lại.
• Một lần nữa, chúng ta sẽ loại bỏ một nửa số dựa trên giá trị mục tiêu cao hoặc thấp hơn giá trị ở giữa.
• Chúng ta sẽ tiếp tục quá trình này cho tới khi tìm thấy mục tiêu hoặc xác định nó không nằm trong danh sách.

Như bạn thấy, do tìm kiếm nhị phân loại bỏ một nửa các giá trị có thể mỗi lần tính toán nên n dù có lớn bao nhiêu cũng không ảnh hưởng tới số lần kiểm tra mảng. Biểu thị điều này bằng ký hiệu Big-O như sau:

O(log(n))

Nhìn chung, Big-O mang tới cho bạn cách nhanh chóng và dễ dàng đánh giá hiệu quả của một thuật toán, giúp bạn dễ phát hiện ra điểm khác biệt khi lập trình.