Phân tích thuật toán
Phân tích hiệu quả thuật toán có thể thực hiện ở hai giai đoạn: trước và sau khi cài đặt.
- Phân tích a priori (A priori analysis): Phân tích lý thuyết. Hiệu quả đo lường bằng giả định các yếu tố khác (tốc độ bộ vi xử lý) không đổi, không ảnh hưởng đến cài đặt.
- Phân tích a posteriori (A posterior analysis): Phân tích thực nghiệm. Thuật toán được cài đặt bằng ngôn ngữ lập trình, chạy trên máy mục tiêu, thu thập thống kê thực tế (thời gian chạy, không gian cần).
Phân tích thuật toán liên quan đến thời gian thực thi của các thao tác. Thời gian chạy của một thao tác được định nghĩa là số lệnh máy tính thực thi cho mỗi thao tác.
Độ phức tạp thuật toán
Giả sử X là thuật toán, N là kích thước 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ả.
- Yếu tố Thời gian: Được tính bằng cách đếm số phép toán chính (ví dụ: so sánh trong thuật toán sắp xếp).
- Yếu tố Không gian: Được tính bằng cách đếm bộ nhớ tối đa mà thuật toán yêu cầu.
Độ phức tạp f(N) của thuật toán cung cấp thời gian chạy và/hoặc không gian lưu trữ cần thiết theo kích thước đầu vào N.
Độ phức tạp Không gian (Space Complexity)
Độ phức tạp không gian đại diện cho lượng bộ nhớ mà thuật toán cần trong vòng đời của nó.
Không gian cần = phần cố định + phần biến đổi.
- Phần cố định: Lưu trữ dữ liệu, biến đơn giản, hằng số, kích thước chương trình... không phụ thuộc vào kích thước bài toán.
- Phần biến đổi: Biến phụ thuộc vào kích thước bài toán: ngăn xếp đệ quy, cấp phát bộ nhớ động, v.v.
Độ phức tạp không gian S(p) = A + Sp(I), trong đó A là phần cố định, Sp(I) là phần biến đổi phụ thuộc đặc tính đầu vào I.
Ví dụ minh họa
THUẬT TOÁN SUM(P, Q) Bước 1 - BẮT ĐẦU Bước 2 - R ← P + Q + 10 Bước 3 - DỪNG
Có 3 biến P, Q, R và 1 hằng số. Do đó S(p) = 1 + 3 = 4 đơn vị (nhân thêm theo kích thước kiểu dữ liệu).
Độ phức tạp Thời gian (Time Complexity)
Độ phức tạp thời gian biểu diễn thời gian cần thiết để thuật toán thực thi xong. Có thể ký hiệu là hàm số t(N), trong đó t(N) là số bước, mỗi bước mất thời gian hằng số.
Ví dụ: cộng hai số nguyên n-bit cần N bước. Tổng thời gian tính toán t(N) = c * n, với c là thời gian cộng hai bit. t(N) tăng tuyến tính khi kích thước đầu vào tăng.