Bài viết được dịch trường đoản cú Big-O notation explained by a self-taught programmer của tác giả Justin Abrahms.

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

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

Nói cho dễ dàng thì Big-O là bí quyết mà mọi lập trình viên nói đến thuật toán. Thuật toán lại là 1 trong những chủ đề kinh sợ khác cơ mà tôi sẽ bàn luận ở 1 bài viết trong tương lai, tuy nhiên đối với nội dung 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 trong chương trình của bạn (thật ra nó cũng gần đúng như vậy). Big-O của 1 hàm được xác định thông qua biện pháp nó làm phản hồi đối với những độ lớn đầu vào khác nhau. Nó sẽ chậm rãi đi thế nào nếu chúng ta bắt nó cách xử lý 1 list gồm 1000 lắp thêm 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ành quả in the_list: if to_check == item: return True return FalseNếu chúng ta gọi item_in_list(2, <1,2,3>), hàm này sẽ chạy khá nhanh. Họ có 1 vòng lặp để soát sổ xem list gồm chứa argument đầu tiên trong hàm không, nếu tất cả thì trả về True. Nếu bọn họ chạy đến cuối danh mục mà vẫn không tìm kiếm thấy thì trả về False.

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

"Orders of magnitude" lại là 1 trong thuật ngữ toán học khác nhưng về cơ bản thì nó chỉ ra sự khác hoàn toàn giữa những cấp độ của nhỏ số. Hãy nghĩ về về sự khác hoàn toàn giữa số 10 cùng số 100. Nếu như bạn nghĩ mang lại 10 người bạn thân nhất so với nghĩ đến 100 người, đó là 1 sự khác biệt rất lớn. Tương tự, khác biệt của 1,000 cùng 10,000 cũng khá lớn (thật ra thì nó là sự khác hoàn toàn 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 câu hỏi ước lượng, miễn là chúng ta vẫn nằm trong một order of magnitude thì đã là sấp xỉ rồi. Nếu khách hàng phải bói toán kẹo nằm trong một cái máy, các bạn sẽ nằm trong 1 order of magnitude nếu như bạn nói là 200. 10,000 cái kẹo thì đang RẤT sai.

*

Hình 1: 1 đồ vật gumball cất số gumball phía bên trong order of magnitude của 200

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

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

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

*

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

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

Hãy coi hàm sau:

def is_none(item): return thành phầm is NoneĐây là một trong những ví dụ ngớ ngẩn, nhưng trong thời điểm tạm thời hãy chịu vậy nhé. Hàm này được hotline là O(1) xuất xắc "độ phức hợp hằng số". Nó có nghĩa là không cần phải biết đầu vào mập đến đâu, nó luôn chỉ cần 1 thời gian cố định để xử lý. Nếu như khách hàng quay lại Wolfram cùng gõ "plot 1", các bạn sẽ thấy rằng nó luôn luôn cố định, bất kể là chúng ta đi sang đề nghị xa mang đến đâu. Nếu như bạn cấp cho nó 1 list gồm 1 triệu số nguyên, nó cũng sẽ chỉ cần số thời gian tương tự như là bạn truyền vào 1 list có một số nguyên. Thời gian thắt chặt và cố định được xem như là tình huống tốt nhất có thể 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 công trình in the_list: for inner_item in the_list: results.append((item, inner_item)) return resultsHàm này ghép mỗi cống phẩm trong danh mục với những 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à một trong những phần của toán tổ hợp (lại 1 thuật ngữ đáng sợ khác). Hàm này (hay thuật toán này, nếu bạn muốn tỏ ra nguy hiểm (hihi)) được xem như là O(n^2). Đó là bởi vì với mỗi nhà cửa trong danh sách (hay n biểu hiện độ phệ đầu vào), bọn họ cần yêu cầu làm thêm n lần tính toán. Nhưng mà n * n = n^2.

Dưới đây là đồ thị so sánh những độ tinh vi trên, nhằm tham khảo. Chúng ta có thể thấy rằng hàm O(n^2) sẽ chậm đi hết sức nhanh trong những khi những hàm cần thời gian cố định để cách xử lý lại giỏi hơn rất nhiều. Điều này đặc biệt tốt đối với xử lý kết cấu dữ liệu, chủ đề mà tôi cũng sẽ nói đến sớm thôi.

Xem thêm: Lệnh Lo Là Gì, Bị Hủy Khi Nào? Lệnh Lo Trong Chứng Khoán Là Gì, Bị Hủy Khi Nào

*

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

Trên đây là những đọc biết bao gồm cấp độ kha khá cao về Big-O, dẫu vậy tôi mong rằng bạn sẽ nhanh chóng rất gần gũi với thuật ngữ này. Có một khóa học coursera có thể cho mình những kỹ càng sâu rộng vào chủ thể này, nhưng xin báo trước là nó đang liên quan rất nhiều đến toán học. Nếu như có bất cứ thứ gì trong bài bác này mà các bạn không hiểu, hãy gửi email cho tôi nhé.