Big-O là gì?

0

Bạn cần mã hiệu quả, nhưng làm thế nào để bạn làm điều đó? Câu trả lời là Big-O. Ký hiệu Big-O là một công cụ hữu ích giúp bạn tính toán mức độ hiệu quả của mã của bạn.

Mọi thứ bạn cần biết về Big-O

Big-O là gì?

Big-O cung cấp cho bạn một cách để tính toán thời gian chạy mã. Bạn có thể tính toán con số đó, nhưng với phương pháp này, có thể dễ dàng phát hiện ra những khác biệt nhỏ. Ví dụ, thời gian chạy từ 20 đến 50 dòng mã là không đáng kể nên không ảnh hưởng nhiều đến việc 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 mà thuật toán cần thực hiện để đánh giá hiệu quả của nó. Cách tiếp cận mã này có thể cực kỳ hiệu quả nếu bạn cần tinh chỉnh mã của mình. Big-O sẽ giúp bạn đo lường các thuật toán khác nhau thông qua các bước cần thiết để chạy và so sánh 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 toán số lượng tất và trả về số lượng của mỗi chiếc tất. Mã này được viết bằng Python nhưng điều đó không ảnh hưởng đến cách chúng tôi đếm 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ụ ngu ngốc và có thể dễ dàng thấy thuật toán nào hiệu quả hơn. Nhưng, trên 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ó chỉ định 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ó chỉ định các giá trị bổ sung cho các khóa riêng lẻ.
  6. Nó tăng từng cái một.
  7. Sau đó, nó lặp lại các bước từ 3 đến 6 với cùng số lần như (indviualSocks – 1).

Số bước để hoàn thành thuật toán một có thể được chỉ ra bằng:

4n + 2

Có 4 bước để hoàn thành n lần. Trong trường hợp này, n sẽ bằng giá trị của numberOfPairs. Cũng có hai bước cần được hoàn thành cùng một lúc. 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

Bây 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

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

Trong ví dụ trên, thuật toán 2 sẽ được hiển thị 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 ảnh hưởng của thuật toán 1 liên quan đến giá trị n. Con số này càng lớn thì thuật toán càng cần hoàn thành nhiều bước.

Mã tuyến tính

Mã tuyến tính

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

Mã bậc hai

Không phải tất cả cá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

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

Biểu đồ mã với ký hiệu Big-O

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

O(n²)

Logarit mã

Mặc dù có nhiều mối quan hệ khác nhưng mối quan hệ cuối cùng chúng ta cần quan tâm là logarit. Một lần nữa, logarit của một số là lũy thừa cần thiết để đạt đến một số cơ số. Ví dụ:

log 2 (8) = 3

Logarit bằng 3 vì nếu cơ số là 2, ta cần lũy thừa của 3 để có 8.

Biểu đồ đường cong

Do đó, mối quan hệ của hàm số lôgarit ngược lại với hàm số mũ. khi mà n ngày càng tăng, số bước cần thiết để chạy thuật toán sẽ ít hơn.

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

  • Bắt đầu với một mảng để tìm nó theo thứ tự từ nhỏ nhất đến lớn nhất.
  • Tiếp theo, kiểm tra giá trị ở giữa phạm vi.
  • Nếu số cao hơn, chúng tôi sẽ xóa các số thấp hơn khỏi kết quả tìm kiếm và nếu số thấp hơn, chúng tôi sẽ xóa các số cao hơn.
  • Bây 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 tôi 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ữa.
  • Chúng tôi sẽ tiếp tục quá trình này cho đến khi chúng tôi tìm thấy mục tiêu hoặc xác định nó không có trong danh sách.

Như bạn có thể thấy, vì tìm kiếm nhị phân loại bỏ một nửa giá trị có thể có trong mỗi phép tính n Cho dù nó có lớn đến đâu, nó cũng không ảnh hưởng đến 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 cung cấp cho bạn một 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ễ dàng phát hiện ra sự khác biệt trong lập trình.

Xem thêm những bài mới Hôm nay trong Tin Mới ?

Leave A Reply

Your email address will not be published.