Cách tính big o án? time complexity — Độ phức tạp của thuật toán

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

Bạn đang xem: Cách tính big o án? time complexity — Độ phức tạp của thuật toán

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

Nói mang lại đơn giản thì Big-O là phương pháp nhưng hầu như thiết kế viên nói tới thuật tân oán. Thuật toán thù lại là 1 trong chủ thể kinh sợ không giống nhưng mà tôi vẫn bàn luận ở một nội dung bài viết trong tương lai, cơ mà so với nội dung bài viết này thì hãy coi 1 thuật toán nghĩa là 1 trong hàm trong chương trình của công ty (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 biện pháp nó phản hồi so với những độ phệ đầu vào khác biệt. Nó sẽ chậm trễ đi thế nào nếu họ bắt nó cách xử trí 1 list tất cả 1000 vật dụng vậy vì 1 list chỉ có một thứ?

Hãy xem đoạn code sau:

def item_in_list(to_check, the_list): for công trình in the_list: if to_kiểm tra == item: return True return FalseNếu họ Gọi item_in_list(2, <1,2,3>), hàm này đã chạy khá nkhô cứng. Chúng ta có một vòng lặp nhằm soát sổ xem list tất cả cất argument trước tiên trong hàm không, ví như bao gồm thì trả về True. Nếu họ chạy mang đến cuối list mà lại 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 sẽ giải thích ý nghĩa của nó tức thì, tuy vậy hãy cùng đối chiếu mẫu cú pháp tân oán học tập này trước vẫn nhé. O(n) tức là "Bậc của N" chính vì hàm O còn được biết đến là hàm bậc (Order). Tôi nghĩ về chính là cũng chính vì họ sẽ khoảng chừng, cơ mà ước tính thì lại liên quan cho "orders of magnitude".

"Orders of magnitude" lại là một trong thuật ngữ toán học không giống mà lại về cơ bản thì nó chỉ ra rằng sự biệt lập giữa các Lever của số lượng. Hãy suy nghĩ về việc khác biệt giữa số 10 và số 100. Nếu các bạn suy nghĩ mang lại 10 fan đồng bọn tuyệt nhất đối với nghĩ mang lại 100 bạn, kia là 1 trong những sự khác hoàn toàn không hề nhỏ. Tương từ bỏ, biệt lập của một,000 cùng 10,000 cũng rất Khủng (thiệt ra thì nó là việc khác hoàn toàn thân 1 cái xe truất phế thải và 1 cái xe bắt đầu dùng vài lần). Hóa ra là trong câu hỏi ước lượng, miễn sao bạn vẫn nằm trong một order of magnitude thì đang là gần đúng rồi. Nếu chúng ta buộc phải đoán thù số kẹo ở trong 1 chiếc máy, bạn sẽ ở trong một order of magnitude nếu như bạn nói là 200. 10,000 loại kẹo thì đang RẤT sai.

Hình 1: 1 sản phẩm công nghệ gumball đựng số gumball phía trong order of magnitude của 200

Trsinh sống lại với Việc đối chiếu O(n), nó tất cả nghĩa rằng trường hợp họ phải ước lượng thời hạn cơ mà nó phải để chạy hàm này với hầu hết độ Khủng đầu vào không giống nhau (ví dụ như một array gồm 1 nhà cửa, 2 chiến thắng, 3 công trình,...), chúng ta đã thấy rằng thời gian dự tính có liên quan mang đến số tòa tháp phía bên trong array. Cái này Hotline là vật dụng thị đường tính. Nghĩa là đường kẻ về cơ bản đã là đường thẳng trường hợp họ vẽ nó ra.

Xem thêm: Luyện Tập Làm Văn Lớp 5: Làm Biên Bản Cuộc Họp Trang 143 Sgk Tiếng Việt 5 Tập 1

Có thể các bạn sẽ phân phát hiện ra rằng nếu như, với đoạn code mẫu sinh sống bên trên, tòa tháp buộc phải tra cứu luôn luôn luôn là item đầu tiên trong danh mục, đoạn code của họ sẽ chạy siêu nhanh! Điều này không không nên, cơ mà Big-O hoàn toàn là nhằm ước tính hiệu suất để làm 1 các bước như thế nào kia trong trường hợp xấu duy nhất. Tình huống xấu nhất đối với đoạn code trên là thiết bị bọn họ sẽ search không thể phía trong các mục. (Thuật ngữ tân oán học tập mang đến điều này là "cận trên")

Nếu bạn muốn xem 1 thiết bị thị màn trình diễn đều hàm này, bạn sẽ bỏ qua hàm O() cùng nạm đổi mới n bởi x. Sau đó thì bạn cũng có thể gõ nó vào Wolfram Altrộn bằng "plot x" với nó vẫn show ra 1 mặt đường chéo cánh. Lí vì bạn cần thay n bởi x là do lịch trình biểu diễn đồ dùng thị của người ta muốn x là tên trở nên bởi vì nó tương quan đến cột x. Cột x đang to ra tự trái qua cần tương xứng với độ Khủng tăng nhiều của array truyền vào hàm của chúng ta. Cột y miêu tả thời gian, cần giả dụ mặt đường thẳng đi lên càng tốt thì nó càng lừ đừ.

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

Vậy thì các ví dụ không giống của chính nó đang cụ nào?

Hãy xem hàm sau:

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

Hình 3: Điểm lưu ý runtime của 1 hàm O(1)

Hãy xem hàm sau:

def all_combinations(the_list): results = <> for nhà cửa in the_list: for inner_thành tựu in the_list: results.append((vật phẩm, inner_item)) return resultsHàm này ghxay mỗi vật phẩm vào menu với phần đông sản phẩm không giống vào menu. Nếu họ truyền vào 1 array <1,2,3>, nó đã 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ổng hợp (lại 1 thuật ngữ kinh sợ khác). Hàm này (tốt thuật toán này, trường hợp bạn có nhu cầu tỏ ra nguy hiểm (hihi)) được xem như là O(n^2). Đó là cũng chính vì cùng với mỗi nhà cửa trong danh sách (xuất xắc n miêu tả độ to đầu vào), bọn họ rất cần phải có tác dụng thêm n lần tính toán. Mà n * n = n^2.

Dưới đấy là thiết bị thị đối chiếu những độ phức tạp bên trên, nhằm tham khảo. Quý khách hàng rất có thể thấy rằng hàm O(n^2) đang chậm chạp đi khôn cùng nhanh hao trong lúc đa số hàm bắt buộc thời hạn thắt chặt và cố định nhằm cách xử trí lại tốt hơn không hề ít. Điều này đặc trưng xuất sắc đối với giải pháp xử lý kết cấu tài liệu, chủ đề cơ mà tôi cũng biến thành nói đến sớm thôi.

Xem thêm: Cách Lưu Ảnh Trên Google Photos Dễ Dàng, Nhanh Chóng, Sao Lưu Ảnh Và Video

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

Trên đấy là đều phát âm biết có cấp độ tương đối cao về Big-O, cơ mà tôi hy vọng rằng bạn sẽ hối hả không còn xa lạ với thuật ngữ này. Có 1 khóa học coursera hoàn toàn có thể cho chính mình các tinh tướng sâu rộng vào chủ đề này, cơ mà xin báo trước là nó đang tương quan tương đối nhiều cho tân oán học. Nếu tất cả bất cứ trang bị gì trong bài này cơ mà bạn thiếu hiểu biết nhiều, hãy gửi gmail mang đến tôi nhé.