Ký hiệu Big-O là gì?

Ký hiệu Big-O là gì?

Bạn đã bao giờ tự hỏi tại sao một chương trình bạn viết lại mất nhiều thời gian để chạy? Có lẽ bạn muốn biết liệu bạn có thể làm cho mã của mình hiệu quả hơn hay không. Hiểu cách chạy mã có thể đưa mã của bạn lên cấp độ tiếp theo. Ký hiệu Big-O là một công cụ tiện dụng để tính toán mã của bạn thực sự hiệu quả như thế nào.





Ký hiệu Big-O là gì?

Ký hiệu Big-O cung cấp cho bạn một cách để tính toán thời gian chạy mã của bạn. Bạn có thể tính thời gian thực tế để mã của mình chạy trong bao lâu, nhưng với phương pháp đó, thật khó để nắm bắt được những khác biệt nhỏ về thời gian. Ví dụ, thời gian từ khi chạy 20 đến 50 dòng mã là rất 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.



cách tăng tốc độ internet trên điện thoại

Ký hiệu Big-O tính số bước mà một thuật toán phải thực hiện để đánh giá hiệu quả của nó. Tiếp cận mã của bạn theo cách này có thể rất hiệu quả nếu bạn cần điều chỉnh mã của mình để tăng hiệu quả. Ký hiệu Big-O sẽ cho phép bạn đo lường các thuật toán khác nhau theo số bước mà nó yêu cầu để chạy và so sánh một cách khách quan hiệu quả của các thuật toán.





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

Hãy xem xét hai chức năng đếm xem có bao nhiêu chiếc tất riêng lẻ trong ngăn kéo. Mỗi hàm lấy số lượng đôi tất và trả về số lượng đôi tất riêng lẻ. Mã được viết bằng Python, nhưng điều đó không ảnh hưởng đến cách chúng tôi đếm số 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 sẽ có thể dễ dàng biết được thuật toán nào hiệu quả hơn. Nhưng để thực hành, chúng ta hãy chạy qua từng cái.



CÓ LIÊN QUAN: Một chức năng trong lập trình là gì?

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



  1. Nó chỉ định một giá trị bằng 0 cho biến cá nhân.
  2. Nó gán một giá trị của một cho biến i.
  3. Nó so sánh giá trị của i với numberOfPairs.
  4. Nó thêm hai vào cá nhân.
  5. Nó chỉ định giá trị gia tăng của các IndividualSocks cho chính nó.
  6. Nó tăng dần từng thứ một.
  7. Sau đó, nó lặp lại qua các bước từ 3 đến 6 với cùng số lần như (indviualSocks - 1).

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

4n + 2

Có bốn bước mà chúng ta 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. Cũng có 2 bước hoàn thành một lần.

Để so sánh, thuật toán 2 chỉ có một bước. Giá trị của numberOfPairs được nhân với hai. Chúng tôi sẽ thể hiện điều đó như:

1

Nếu nó chưa rõ ràng, bây giờ chúng ta có thể dễ dàng thấy rằng 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 chi tiết về số bước. Để đơn giản hóa ký hiệu, chúng ta chỉ có thể nêu mức độ hiệu quả.

Trong các ví dụ trên, thuật toán 2 sẽ được biểu thị như sau:

O(1)

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

O(n)

Ảnh chụp nhanh này cho chúng ta biết hiệu quả của thuật toán một được gắn với giá trị của n như thế nào. Số càng lớn thì thuật toán sẽ cần phải hoàn thành nhiều bước hơn.

Mã tuyến tính

Tín dụng hình ảnh: Nick Fledderus / Dự án danh từ

Bởi vì chúng ta không biết giá trị của n, sẽ hữu ích hơn nếu bạn nghĩ xem giá trị của n ảnh hưởng như thế nào đến lượng mã cần chạy. Trong thuật toán 1, chúng ta có thể nói rằng mối quan hệ là tuyến tính. Nếu bạn vẽ biểu đồ số bước so với giá trị của n, bạn sẽ có 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. Hãy tưởng tượng bạn có một mảng 2D và bạn muốn tìm kiếm một giá trị trong mảng. Bạn có thể tạo một thuật toán như thế này:

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. Vì vậy, số bước đơn giản hóa sẽ là n * n hoặc n².

cách xóa dòng ngang trong word

Tín dụng hình ảnh: Nick Fledderus / Dự án danh từ

Mối quan hệ này là mối quan hệ bậc hai, có nghĩa là số bước trong thuật toán của chúng ta tăng lên theo cấp số nhân với n. Trong ký hiệu Big-O, bạn sẽ viết nó là:

O(n²)

CÓ LIÊN QUAN: Các công cụ hữu ích để kiểm tra, làm sạch và tối ưu hóa tệp CSS

Mã lôgarit

Mặc dù có nhiều mối quan hệ khác, mối quan hệ cuối cùng mà chúng ta sẽ xem xét là mối quan hệ logarit. Để làm mới bộ nhớ của bạn, nhật ký của một số là giá trị lũy thừa cần thiết để đạt được một số cho trước một cơ số. Ví dụ:

log 2 (8) = 3

Nhật ký bằng ba vì nếu cơ số của chúng tôi là 2, chúng tôi sẽ cần một giá trị lũy thừa của 3 để có được số 8.

Tín dụng hình ảnh: Nick Fledderus / Dự án danh từ

Vì vậy, quan hệ của một hàm số lôgarit ngược lại với một quan hệ cấp số nhân. Khi n tăng lên, cần có ít bước mới hơn để chạy thuật toá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 thuật toán có thể phát triển chậm hơn n? Một ví dụ điển hình về điều này là tìm kiếm nhị phân. Hãy xem xét một thuật toán để tìm kiếm một số trong một mảng các giá trị duy nhất.

  • Chúng ta sẽ bắt đầu với một mảng để tìm kiếm theo thứ tự từ nhỏ nhất đến lớn nhất.
  • Tiếp theo, chúng ta sẽ kiểm tra giá trị ở giữa mảng.
  • Nếu số của bạn cao hơn, chúng tôi sẽ loại trừ các số thấp hơn trong tìm kiếm của mình và nếu số thấp hơn, chúng tôi sẽ loại trừ các số cao hơn.
  • Bây giờ, chúng ta sẽ xem xét số chính giữa của các số còn lại.
  • Một lần nữa, chúng tôi sẽ loại trừ một nửa số dựa trên việc liệu giá trị mục tiêu của chúng tôi cao hơn hay thấp hơn giá trị trung bình.
  • 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 của mình hoặc xác định rằng 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ó mỗi lần vượt qua, khi n lớn hơn, ảnh hưởng đến số lần chúng tôi kiểm tra mảng hầu như không bị ảnh hưởng. Để thể hiện điều này trong ký hiệu Big-O, chúng tôi sẽ viết:

O(log(n))

Tầm quan trọng của ký hiệu Big-O

Big-O Nation cung cấp cho bạn một cách nhanh chóng và dễ dàng để thông báo mức độ hiệu quả của một thuật toán. Điều này giúp bạn dễ dàng quyết định hơn giữa các thuật toán khác nhau. Điều này có thể đặc biệt hữu ích nếu bạn đang sử dụng một thuật toán từ thư viện và không nhất thiết phải biết mã trông như thế nào.

chạy 16 bit trên 64 bit windows 10

Khi bạn lần đầu tiên học viết mã, bạn bắt đầu với các hàm tuyến tính. Như bạn có thể thấy từ biểu đồ trên, điều đó sẽ giúp bạn tiến rất xa. Nhưng khi bạn trở nên có kinh nghiệm hơn và bắt đầu xây dựng mã phức tạp hơn, hiệu quả bắt đầu trở thành một vấn đề. Sự hiểu biết về cách định lượng hiệu quả của mã của bạn sẽ cung cấp cho bạn các công cụ bạn cần để bắt đầu điều chỉnh nó cho hiệu quả và cân nhắc những ưu và nhược điểm của các thuật toán.

Đăng lại Đăng lại tiếng riu ríu E-mail 10 lỗi lập trình và mã hóa phổ biến nhất

Sai lầm về mã hóa có thể dẫn đến rất nhiều vấn đề. Những mẹo này sẽ giúp bạn tránh những lỗi lập trình và giữ cho mã của bạn có ý nghĩa.

Đọc tiếp Chủ đề liên quan
  • Lập trình
  • Lập trình
Giới thiệu về tác giả Jennifer Seaton(21 bài báo đã xuất bản)

J. Seaton là một nhà văn khoa học chuyên nghiên cứu về các chủ đề phức tạp. Cô có bằng Tiến sĩ tại Đại học Saskatchewan; nghiên cứu của cô tập trung vào việc sử dụng học tập dựa trên trò chơi để tăng mức độ tương tác trực tuyến của sinh viên. Khi cô ấy không làm việc, bạn sẽ thấy cô ấy đang đọc sách, chơi trò chơi điện tử hoặc làm vườn.

Xem thêm từ Jennifer Seaton

Theo dõi bản tin của chúng tôi

Tham gia bản tin của chúng tôi để biết các mẹo công nghệ, đánh giá, sách điện tử miễn phí và các ưu đãi độc quyền!

Bấm vào đây để đăng ký