Python - Phân tích thuật toán

Phân tích thuật toán

Hiệu quả của một thuật toán có thể được phân tích ở hai giai đoạn khác nhau, trước khi thực hiện và sau khi thực hiện. Chúng là những thứ sau -

A Priori Analysis- Đây là một phân tích lý thuyết của một thuật toán. Hiệu quả của một thuật toán được đo lường bằng cách giả định rằng tất cả các yếu tố khác, ví dụ, tốc độ bộ xử lý, là không đổi và không ảnh hưởng đến việc triển khai.
A Posterior Analysis- Đây là phân tích thực nghiệm của một thuật toán. Thuật toán đã chọn được thực hiện bằng ngôn ngữ lập trình. Điều này sau đó được thực hiện trên máy tính đích. Trong phân tích này, số liệu thống kê thực tế như thời gian chạy và không gian cần thiết, được thu thập.

Độ phức tạp của thuật toán

Giả sử X là một thuật toán và n là kích thước của dữ liệu đầu vào, thời gian và không gian mà thuật toán X sử dụng là hai yếu tố chính quyết định hiệu quả của X.

Time Factor - Thời gian được đo bằng cách đếm số lượng các thao tác chính như so sánh trong thuật toán sắp xếp.
Space Factor - Không gian được đo bằng cách đếm không gian bộ nhớ lớn nhất mà thuật toán yêu cầu.

Độ phức tạp của một thuật toán f(n) cung cấp thời gian chạy và / hoặc không gian lưu trữ theo yêu cầu của thuật toán về n như kích thước của dữ liệu đầu vào.

Không gian phức tạp

Độ phức tạp không gian của một thuật toán biểu thị lượng không gian bộ nhớ mà thuật toán yêu cầu trong vòng đời của nó. Không gian được yêu cầu bởi một thuật toán bằng tổng của hai thành phần sau:

Một phần cố định là không gian cần thiết để lưu trữ dữ liệu và biến nhất định, độc lập với quy mô của vấn đề. Ví dụ, các biến và hằng số đơn giản được sử dụng, kích thước chương trình, v.v.
Một phần biến là một không gian được yêu cầu bởi các biến, kích thước của nó phụ thuộc vào kích thước của bài toán. Ví dụ, cấp phát bộ nhớ động, không gian ngăn xếp đệ quy, v.v.

Độ phức tạp không gian S (P) của bất kỳ thuật toán P nào là S (P) = C + SP (I), trong đó C là phần cố định và S (I) là phần biến của thuật toán, phụ thuộc vào đặc tính cá thể I. Sau đây là một ví dụ đơn giản cố gắng giải thích khái niệm -

Algorithm: SUM(A, B)
Step 1 -  START
Step 2 -  C ← A + B + 10
Step 3 -  Stop

Ở đây chúng ta có ba biến A, B, C và một hằng số. Do đó S (P) = 1 + 3. Bây giờ, không gian phụ thuộc vào kiểu dữ liệu của các biến và kiểu hằng đã cho và nó sẽ được nhân lên tương ứng.

Thời gian phức tạp

Độ phức tạp thời gian của một thuật toán biểu thị lượng thời gian mà thuật toán yêu cầu để chạy đến khi hoàn thành. Yêu cầu về thời gian có thể được định nghĩa như một hàm số T (n), trong đó T (n) có thể được đo bằng số bước, miễn là mỗi bước tiêu thụ thời gian không đổi.

Ví dụ, phép cộng hai số nguyên n bit sẽ mất ncác bước. Do đó, tổng thời gian tính toán là T (n) = c ∗ n, trong đó c là thời gian thực hiện phép cộng hai bit. Ở đây, chúng tôi quan sát thấy rằng T (n) tăng tuyến tính khi kích thước đầu vào tăng lên.