Big o notation là gì

     

Bài viết được dịch tự Big-O notation explained by a self-taught programmer của người sáng tác Justin Abrahms.

Bạn đang xem: Big o notation là gì

Kí hiệu Big-O đã từng là 1 trong những thuật ngữ xứng đáng sợ đối với tôi. Tôi đang nghĩ đó là biện pháp mà phần đông lập trình viên "đích thực" nói đến code của họ. Nó càng kinh sợ hơn bởi vì những chú giải mang ý nghĩa chất học tập thuật (ví dụ như Wikipedia) không làm cho nó dễ dàng nắm bắt hơn chút nào. Điều tôi muốn kể đến ở bài bác này là số đông khái niệm cơ bạn dạng của Big-O chưa tới nỗi cực nhọc như vậy.

Nói cho đơn giản và dễ dàng thì Big-O là giải pháp mà đầy đủ lập trình viên nói tới thuật toán. Thuật toán lại là một trong chủ đề kinh sợ khác nhưng mà tôi sẽ trao đổi ở 1 nội dung bài viết trong tương lai, nhưng lại đối với bài viết này thì nên coi 1 thuật toán nghĩa là một trong những hàm vào chương trình của doanh nghiệp (thật ra nó cũng xấp xỉ đúng như vậy). Big-O của 1 hàm được khẳng định thông qua phương pháp nó bội nghịch hồi so với những độ lớn nguồn vào khác nhau. Nó sẽ chậm rãi đi thế nào nếu chúng ta bắt nó giải pháp xử lý 1 list gồm 1000 sản phẩm công nghệ thay vì chưng 1 list chỉ có 1 thứ?

Hãy xem đoạn code sau:

def item_in_list(to_check, the_list): for thắng lợi in the_list: if to_check == item: return True return FalseNếu bọn họ gọi item_in_list(2, <1,2,3>), hàm này đang chạy hơi nhanh. Chúng ta có 1 vòng lặp để soát sổ xem list gồm chứa argument trước tiên trong hàm không, nếu có thì trả về True. Nếu họ chạy đến cuối menu mà vẫn không tìm thấy thì trả về False.

"Độ phức tạp" của hàm này là O(n). Tôi đang giải thích chân thành và ý nghĩa của nó ngay, mà lại hãy cùng phân tích dòng cú pháp toán học này trước vẫn nhé. O(n) tức là "Bậc của N" cũng chính vì hàm O còn được nghe biết là hàm bậc (Order). Tôi nghĩ kia là bởi vì chúng ta đang mong lượng, mà ước lượng thì lại liên quan đến "orders of magnitude".

"Orders of magnitude" lại là 1 thuật ngữ toán học tập khác nhưng mà về cơ bản thì nó chỉ ra rằng sự biệt lập giữa những cấp độ của bé số. Hãy nghĩ về sự khác biệt giữa số 10 với số 100. Nếu bạn nghĩ đến 10 người bạn bè nhất đối với nghĩ đến 100 người, đó là 1 trong những sự khác hoàn toàn rất lớn. Tương tự, khác hoàn toàn của 1,000 với 10,000 cũng rất lớn (thật ra thì nó là sự khác biệt giữa 1 chiếc xe phế thải với 1 chiếc xe mới cần sử dụng vài lần). Hóa ra là trong việc ước lượng, miễn là chúng ta vẫn nằm trong 1 order of magnitude thì đã là giao động rồi. Nếu bạn phải đoán số kẹo nằm trong 1 cái máy, bạn sẽ nằm trong một order of magnitude nếu khách hàng nói là 200. 10,000 chiếc kẹo thì đang RẤT sai.

*

Hình 1: 1 vật dụng gumball cất số gumball bên trong order of magnitude của 200

Trở lại với câu hỏi phân tích O(n), nó gồm nghĩa rằng nếu chúng ta phải mong lượng thời hạn mà nó bắt buộc để chạy hàm này với đông đảo độ khủng đầu vào không giống nhau (ví dụ như 1 array bao gồm 1 item, 2 item, 3 item,...), chúng ta sẽ thấy rằng thời gian ước tính có tương quan đến số item phía trong array. Tính năng này gọi là trang bị thị tuyến đường tính. Nghĩa là đường kẻ về cơ phiên bản sẽ là con đường thẳng nếu chúng ta vẽ nó ra.

Xem thêm: Ngữ Văn Lớp 6 Trang 48 Thực Hành Tiếng Việt, Soạn Văn 6 Trang 48 Chân Trời Sáng Tạo

Có thể bạn sẽ phát hiện ra rằng nếu, với đoạn code mẫu ở trên, item phải tìm luôn luôn luôn là item đầu tiên trong list, đoạn code của chúng ta sẽ chạy khôn cùng nhanh! Điều này sẽ không sai, tuy nhiên Big-O trọn vẹn là để ước tính hiệu suất để gia công 1 các bước nào đó trong trường hợp xấu nhất. Trường hợp xấu nhất so với đoạn code trên là thứ họ đang tìm không hề nằm trong list. (Thuật ngữ toán học cho cái này là "cận trên")

Nếu bạn có nhu cầu xem 1 đồ dùng thị màn biểu diễn những hàm này, bạn sẽ bỏ qua hàm O() cùng thay đổi mới n bằng x. Tiếp đến thì bạn cũng có thể gõ nó vào Wolfram Alpha bằng "plot x" và nó đang show ra 1 con đường chéo. Lí do bạn phải thay n bằng x là do chương trình biểu diễn đồ thị của họ muốn x là tên gọi biến bởi vì nó liên quan đến cột x. Cột x vẫn to ra từ bỏ trái qua phải tương xứng với độ lớn tăng vọt của array truyền vào hàm của bạn. Cột y thể hiện thời gian, phải nếu mặt đường thẳng đi lên càng tốt thì nó càng chậm.

*

Hình 2: Đặc điểm runtime của một hàm O(n)

Vậy thì những ví dụ khác của nó sẽ vắt nào?

Hãy coi hàm sau:

def is_none(item): return thành tích is NoneĐây là 1 ví dụ ngớ ngẩn, nhưng tạm thời hãy chịu đựng vậy nhé. Hàm này được gọi là O(1) tuyệt "độ tinh vi hằng số". Nó tức là không nên biết đầu vào lớn đến đâu, nó luôn chỉ cần 1 thời gian cố định để xử lý. Nếu bạn quay lại Wolfram với gõ "plot 1", các bạn sẽ thấy rằng nó luôn luôn cố định, bất cứ là các bạn đi sang nên xa đến đâu. Nếu như khách hàng cấp mang đến nó 1 list gồm một triệu số nguyên, nó cũng sẽ chỉ việc số thời gian tương tự như là bạn truyền vào 1 list có 1 số nguyên. Thời gian cố định và thắt chặt được coi là tình huống cực tốt của 1 hàm.

*

Hình 3: Đặc điểm runtime của một hàm O(1)

Hãy xem hàm sau:

def all_combinations(the_list): results = <> for thành quả in the_list: for inner_item in the_list: results.append((item, inner_item)) return resultsHàm này ghép mỗi chiến thắng trong danh sách với các item không giống trong list. Nếu họ truyền vào 1 array <1,2,3>, nó đang trả về <(1,1) (1,2), (1,3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)>. Cái này là 1 phần của toán tổ hợp (lại 1 thuật ngữ khiếp sợ khác). Hàm này (hay thuật toán này, nếu bạn có nhu cầu tỏ ra nguy hiểm (hihi)) được xem là O(n^2). Đó là chính vì với mỗi tòa tháp trong list (hay n biểu lộ độ to đầu vào), bọn họ cần đề nghị làm thêm n lần tính toán. Nhưng n * n = n^2.

Dưới đấy là đồ thị so sánh những độ tinh vi trên, để tham khảo. Chúng ta cũng có thể thấy rằng hàm O(n^2) sẽ chậm trễ đi rất nhanh trong lúc những hàm bắt buộc thời gian cố định và thắt chặt để giải pháp xử lý lại xuất sắc hơn siêu nhiều. Điều này quan trọng tốt đối với xử lý cấu trúc dữ liệu, chủ thể mà tôi cũng trở thành nói mang lại sớm thôi.

Xem thêm: Sgk Nghề Điện Dân Dụng 11 Bản Chuẩn, Điện Dân Dụng

*

Figure 4: so sánh O(n2) vs O(n) vs O(1)

Trên đấy là những hiểu biết bao gồm cấp độ tương đối cao về Big-O, cơ mà tôi ước ao rằng các bạn sẽ nhanh chóng không còn xa lạ với thuật ngữ này. Có 1 khóa học coursera có thể cho bạn những góc cạnh sâu rộng vào chủ thể này, nhưng xin báo trước là nó đã liên quan không ít đến toán học. Giả dụ có bất cứ thứ gì trong bài này mà chúng ta không hiểu, hãy gửi email cho tôi nhé.