Phân tích thuật toán
Phân tích hiệu quả của một thuật toán có thể được thực hiện ở hai giai đoạn khác nhau, trước khi triển khai và sau khi thực hiện, như
Phân tích tiên nghiệm - Đây được định nghĩa là phân tích lý thuyết của một thuật toán. Hiệu quả của 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 độ của bộ xử lý, không đổi và không ảnh hưởng đến việc triển khai.
Phân tích hậu nghiệm - Đây được định nghĩa 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. Tiếp theo, thuật toán đã chọn được thực thi 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ân tích thuật toán liên quan đến việc thực thi hoặc thời gian chạy của các hoạt động khác nhau có liên quan. Thời gian chạy của một thao tác có thể được xác định bằng số lượng lệnh máy tính được thực thi trên mỗi thao tác.
Độ phức tạp của thuật toán
Giả sử X được coi là một thuật toán và N được coi là kích thước của dữ liệu đầu vào, thời gian và không gian được thực hiện bởi Thuật toán X là hai yếu tố chính quyết định hiệu quả của X.
Yếu tố thời gian - Thời gian được tính toán hoặc đo lường bằng cách đếm số lượng các hoạt động chính như so sánh trong thuật toán sắp xếp.
Hệ số không gian - Không gian được tính toán hoặc đo bằng cách đếm không gian bộ nhớ tối đa mà thuật toán yêu cầu.
Độ phức tạp của thuật toán f (N) cung cấp thời gian chạy và / hoặc không gian lưu trữ cần thiết của thuật toán đối với N là kích thước của dữ liệu đầu vào.
Sự phức tạp về không gian
Độ 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ớ cần thiết của thuật toán trong vòng đời của nó.
Không gian cần thiết của 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 (tức là biến và hằng số đơn giản, kích thước chương trình, v.v.), không phụ thuộc vào quy mô của vấn đề.
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ó hoàn toàn phụ thuộc vào kích thước của bài toán. Ví dụ:không gian ngăn xếp đệ quy, cấp phát bộ nhớ động, 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) =A + Sp (I) Trong đó A được coi là phần cố định và S (I) được coi 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 giúp giải thích khái niệm
Thuật toán
SUM(P, Q) Step 1 - START Step 2 - R ← P + Q + 10 Step 3 - Stop
Ở đây chúng ta có ba biến P, Q và R và một hằng số. Do đó S (p) =1 + 3. Giờ đây, không gian phụ thuộc vào kiểu dữ liệu của các kiểu và biến hằng số đã cho và nó sẽ được nhân lên tương ứng.
Độ phức tạp về thời gian
Độ phức tạp về thời gian của một thuật toán là sự thể hiện lượng thời gian mà thuật toán yêu cầu để thực thi đến khi hoàn thành. Yêu cầu về thời gian có thể được biểu thị hoặc định nghĩa dưới dạng 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 có thời gian không đổi.
Ví dụ, trong trường hợp cộng hai số nguyên n bit, N bước được thực hiện. Do đó, tổng thời gian tính toán là t (N) =c * n, trong đó c là thời gian dùng để cộng hai bit. Ở đây, chúng tôi nhận thấy rằng t (N) phát triển tuyến tính khi kích thước đầu vào tăng lên.