CÁCH TÍNH ĐỘ PHỨC TẠP CỦA THUẬT TOÁN

      19

Khi tuyển lựa thuật toàn để xử lý một vấn đề cụ thể. Điều đầu tiên các lập trình sẵn viên cần chăm chú đó là độ tinh vi của thuật toán. Để tính độ phức tạp của thuật toán bọn họ dựa trên hai yếu tố: Độ phức tạp về thời hạn chạy thuật toán (số lần triển khai phép tính) với độ phức tạp về không gian (vùng nhớ lưu lại trữ). Bọn họ sử dụng ký tự Big-O để phân loại những thuật toán dựa trên thời gian và không khí khi tài liệu đầu vào tăng lên.

Bạn đang xem: Cách tính độ phức tạp của thuật toán

Độ phức hợp của thuât toán coi như một hàm gồm ký hiệu là Big-O. Với thông số n là kích cỡ đầu vào, O là kịch bạn dạng trong trường phù hợp tăng trưởng xấu nhất. Tuyệt nói giải pháp khác, Big-O là giám sát thời gian chạy lâu tốt nhất của một thuật toán.


Nội dung của bài

2 những quy tắc trong giám sát và đo lường độ phức hợp của thuật toán

Một số chỉ số độ phức hợp của thuật toán theo cường độ tăng dần

Big O NotationNameMô tả
O(1)ConstantSố phép tính là hằng số, không phụ thuộc vào dữ liệu đầu vào. Vd: a + b.
O(log n)LogarithmicSố phép tính (thời gian thực hiện) tăng theo kích cỡ dữ liệu theo hàmlogarit. Vd: tìm kiếm kiếm nhị phân.
O(n)LinearSố phép tính phụ thuộc vào tài liệu đầu vào theo 1 biến. Vd: tìm kiếm tuyến đường tính.
O(n log n)LinearithmicTổng đúng theo của n với logn (lồng nhau). Vd: Heap sort, Merge sort.
O(n2)QuadraticVòng lặp lồng nhau. Ví dụ tìm xem trong tập đúng theo có thành phần trùng nhau không.
O(n3)CubicBa vòng lặp lồng nhau. Lấy một ví dụ tính bài bác toán: 3*x + 5*y + 9 * z = 100
O(2n)ExponentialThời gian chạy theo cấp số nhân (cơ số 2) tức là các phép tính được thực hiện bởi một thuật toán đã tăng gấp hai mỗi khi nguồn vào tăng lên.

Xem thêm: Cách Khắc Chế Poppy - Trong Liên Minh Huyền Thoại

O(n!)FactorialThời gian chạy giai quá như hoán đổi một chuỗi.

Tôi sẽ bổ sung cập nhật các ví dụ ví dụ trong thời gan tới.

O(log n), O(1) O(n) O(n log n) O(n^2) O(2^n) O(n!) Operations Elements

Các luật lệ trong đo lường và tính toán độ phức hợp của thuật toán

Quy tắc vứt hằng số

Nếu đoạn chương trình p có thời gian thực hiện tại T(n) = O(c1.f(n)) với c1 là 1 hằng số dươngthì rất có thể coi đoạn công tác đó có độ phức tạp tính toán là O(f(n)).

Quy tắc cộng – lấy cực hiếm max

Coi T1(n) với T2(n) là thời gian thực hiện tại của hai đoạn chương trình B1 với B2. Trong các số ấy T1(n)=O(f(n)), T2(n)=O(g(n)) thì thời gian thực hiện tại của đoạn hai công tác đó nối liền nhau là T(n)=O(max(f(n),g(n)))

Ví dụ:

Lệnh gán x +=15 tốn một hằng thời hạn hay O(1), lệnh đọc dữ liệu readln(x) tốn một hằng thời gian hay O(1).Vậy thời hạn thực hiện nay cả hai lệnh trên nối tiếp nhau là O(max(1,1))=O(1)

Quy tắc nhân

Coi T1(n) với T2(n) là thời gian thực hiện tại của nhì đoạn lịch trình B1 và B2 với T1(n) = O(f(n)), T2(n) = O(g(n)) thì thời gian thực hiện nay của đoạn nhì đoạn công tác đó lồng nhau là T(n) = O(f(n).g(n))

Quy tắc tổng quát

Thời gian tiến hành mỗi lệnh gán là O(1)Thời gian thực hiện mệnh đề if…else là thời gian lớn nhất thực hiện khối lệnh vào if hoặc trong else. Thời hạn kiểm tra đk là O(1)Thời gian triển khai chuỗi lệnh tuần từ được xác minh bằng luật lệ cộng. Có nghĩa là thời gian triển khai một lệnh lâu độc nhất vô nhị trong chuỗi lệnh.Thời gian triển khai vòng lặp là tổng thể lần tiến hành khối lệnh trong thân vòng lặp. Nếu thời gian thực hiện khối lệnh vào thân vòng lặp không đổi thì thời gian thực hiện vòng lặp là tích của số bước triển khai vòng lặp và thời hạn thực hiện tại thân vòng lặp.

Ví dụ setup thuật toán nổi bọt bằng ngôn từ Python:

def bubble_sort(arr): n = len(arr) # chú tâm qua tất cả các phần tử của mảng for i in range(n): # 1 for j in range(0, n-i-1): # 2 # lưu ý qua các phần tử của mảng tự 0 đén n-i-1 # Đổi khu vực nếu tìm kiếm thấy bộ phận lớn hơn if arr > arr : # 3 arr, arr = arr, arr # 4Ta thấy vào chương trình gồm một lệnh lặp 1, lồng trong lệnh lặp 1 là lệnh lặp 2. Lồng trong lệnh lặp 2 là lệnh đk 3, trong lệnh đk 3 là khối lệnh 4.Khối lệnh 4 thực ra là bố lệnh:

temp = arrarr = arrarr = tempChúng ta đang phân tích từ trong ra ngoài:

Khối 3 lệnh trên tốn thời gian là O(1), câu lệnh đk cũng tốn thời gian là O(1). Vì chưng đó thời gian thực hiện tại lệnh 3 là O(1).

Vòng lặp 2 chạy n-i lần, các lần O(1) nên thời gian chạy vòng lặp 2 là O((n-i) * 1) = O(n-i).

Vòng lặp 1 tất cả i chạy tự 0 mang đến n-1, từ kia to có thời gian thực hiện vòng lặp 1 hay độ tinh vi của thuật toán là: O(n^2)

*

Tổng kết

Tính toán độ phức hợp của thuật toán có lẽ hơi nặng nề hiểu với những người dân mới học lập trình. Tôi sẽ nạm gắng bổ sung nhiều lấy một ví dụ trực quan hơn trong thời hạn tới.

Tham khảo:https://adrianmejia.com/most-popular-algorithms-time-complexity-every-programmer-should-know-free-online-tutorial-course