Cách đánh giá độ phức tạp của thuật toán

     

Mở đầu

Là một lập trình sẵn viên, có lẽ rằng bạn đang từng không ít nghe tới định nghĩa "Độ phức tạp của thuật toán". Không hề ít người cho rằng độ tinh vi của thuật toán thay mặt cho thời hạn chạy cấp tốc hay chậm của một chương trình, nhưng mà liệu đây có phải là 1 trong quan niệm đúng? bài viết dưới trên đây sẽ cho bạn cái nhìn tổng quan về độ phức hợp của 1 thuật toán.

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

Tại sao cần đo độ tinh vi của thuật toán

Thông hay khi giải quyết và xử lý 1 bài bác toán, bạn có thể đưa ra các giải thuật khác biệt nhưng sẽ phải lựa chọn một giải thuật xuất sắc nhất. Thông thường thì ta sẽ địa thế căn cứ vào những tiêu chuẩn sau:

Giải thuật đúng đắn.

Giải thuật solo giản.

Giải thuật thực hiện nhanh.

Để chất vấn tính đúng đắn của 1 giải thuật, ta hay sẽ yêu cầu thử nó với một bộ dữ liệu nào kia rồi so sánh kết quả thu được với công dụng đã biết. Tuy vậy điều này không chắc hẳn rằng vì rất có thể giải thuật này đúng với bộ tài liệu này tuy thế lại không nên với bộ dữ liệu khác. Tính đúng chuẩn của 1 giải thuật cần được minh chứng bằng toán, trợ thời thời bọn họ không kể ở đây.

Đối với những chương trình chỉ sử dụng 1 vài lần thì yêu ước giải thuật dễ dàng sẽ được ưu tiên vì họ cần 1 giải thuật dễ hiểu, dễ download đặt, ở đây không đề cao vấn đề thời gian chạy vì chúng ta chỉ chạy 1 vài ba lần.

Xem thêm: Nevertheless Cách Dùng However Và Nevertheless, Cách Dùng However, Nevertheless

Tuy nhiên, khi một chương trình thực hiện nhiều lần, yêu mong tiết kiệm thời hạn sẽ được quan trọng đặc biệt ưu tiên. Mặc dù nhiên, thời gian thực hiện công tác lại dựa vào vào rất nhiều yếu tố như: cấu hình máy tính, ngữ điệu sử dụng, trình biên dịch, tài liệu đầu vào, ... Cho nên ta khi so sánh 2 giải thuật đã được implement, chưa chắc chương trình chạy nhanh hơn đã gồm giải thuật tốt hơn. "Độ phức tạp của thuật toán" ra đời để giải quyết và xử lý vấn đề này.

Cách để tính độ tinh vi của thuật toán

Độ phức tạp của một thuật toán là một hàm nhờ vào vào độ béo của tài liệu đầu vào.Tìmxem 1 đối tượng người dùng có trong list N phần tử hay không?, bố trí tăng dần dãy sốgồm N số, ... N sống đây chính là độ khủng của dữ liệu đầu vào

Để mong lượng độ phức hợp của một thuật toán, người ta hay được sử dụng khái niệm bậc O-lớn với bậc Theta (Θ)

1. Big O

Ở trên đây ta dùng một đại lượng bao quát là tài nguyên cần dùng R(n). Đó rất có thể là con số phép tính (có thể tính cả chu kỳ truy nhập bộ nhớ, hoặc ghi vào cỗ nhớ); nhưng cũng rất có thể là thời gian thực hiện công tác (độ tinh vi về thời gian) hoặc dung lượng bộ nhớ lưu trữ cần đề nghị cấp để chạy công tác (độ phức hợp về ko gian).

1.1 Định nghĩa

Giả sử f(n) với g(n) là những hàm thực ko âm của đối số nguyên ko âm n. Tanói "g(n) là O của f(n)" với viết là: g(n) = O(f(n)) nếu tồn tại những hằng sốdương C với n0 sao cho g(n) = n0

*

1.2 bí quyết tính

Độ phức tạp thống kê giám sát của giải thuật: O(f(n))

• Việc khẳng định độ phức tạp thống kê giám sát của lời giải trong thực tế hoàn toàn có thể tính bằng một vài quy tắc đơn giản sau:

– Quy tắc quăng quật hằng số:

T(n) = O(c.f(n)) = O(f(n)) cùng với c là một trong những hằng số dương– Quy tắc rước max:

T(n) = O(f(n)+ g(n)) = O(max(f(n), g(n)))– luật lệ cộng:

T1(n) = O(f(n)) T2(n) = O(g(n)) T1(n) + T2(n) = O(f(n) + g(n))– phép tắc nhân:

Đoạn chương trình có thời gian thực hiện T(n)=O(f(n)) Nếu tiến hành k(n) lần đoạn chương trình với k(n) = O(g(n)) thì độ tinh vi sẽ là O(g(n).f(n))

*

1.3 Ví dụ

Ví dụ 1:

s=n*(n-1) /2;Trong lấy ví dụ trên, độ phức hợp của thuật toán là O(1)

Ví dụ 2:

s = 0; // O(1)for (i=0; iSố lần thực hiện phép toán phường = phường * x / j là n(n-1) / 2

=> Độ phức hợp của đoạn code này là O(1) + O(1) + O(n(n-1)/2) + O(1) + O(1) = O(n2)

Ví dụ 3:

for (i= 1;i=> Độ phức tạp của thuật toán này là: O(nmax(nm, x*z))

Theta với Omega

Tương trường đoản cú như Big O, trường hợp như kiếm được các hằng số C, k1, k2 hồ hết dương, không phụthuộc vào n, làm sao để cho với những số n đầy đủ lơn, những hàm R(n), f(n) và h(n) đa số dươngvà R(n) >= C.f(n) va k1.h(n) = thì ta nói thuật toán có độphức tạp cỡ to hơn Omega(f(n)) với đúng bởi cỡ Theta(h(n))

Chúng ta hoàn toàn có thể hiểu Big(O), Omega, Theta tựa như những hàm tiềm cận của hàm tính độ phứctạp của thuật toán.

*
*

Kết luận

Bài viết trên đã chỉ dẫn 1 cái nhìn tổng quan liêu về độ phức hợp của thuật toán. Rằngđó không chỉ thay mặt cho thời hạn chạy nhanh/ chậm của một chương trình cơ mà nóđại diện cho những hành động của khối hệ thống khi form size đầu vào tăng lên.

Hy vọng sau nội dung bài viết này, mỗi khi chúng ta đặt tay viết 1 đoạn chương trình nào đó,hãy cân nặng nhắc, thống kê giám sát để đoạn chương trình gồm độ tinh vi trong mức đến phép.

Xem thêm: Hô Hấp Diễn Ra Mạnh Nhất Trong Trường Hợp Nào Sau Đây? Hô Hấp Diễn Ra Mạnh Nhất Trong Trường Hợp Nào

Cám ơn các bạn đã dành thời gian đọc bài.

Nguồn tham khảo:

https://vi.wikipedia.org/wiki/Độ_phức_tạp_thuật_toánhttp://kcntt.duytan.edu.vn/Home/ArticleDetail/vn/168/2006/xac-dinh-do-phuc-tap-thuat-toan://kcntt.duytan.edu.vn/Home/ArticleDetail/vn/168/2006/xac-dinh-do-phuc-tap-thuat-toanhttp://tek.eten.vn/danh-gia-do-phuc-tap-thuat-toan