Phân tích tiệm cận
Sử dụng phân tích tiệm cận để hình dung hiệu năng thuật toán dựa trên kích thước đầu vào. Không tính thời gian chạy chính xác, mà tìm mối quan hệ giữa thời gian chạy và kích thước đầu vào. Theo dõi thời gian chạy khi kích thước đầu vào tăng.
Đối với độ phức tạp không gian, mục tiêu tìm hàm lượng không gian bộ nhớ chính chiếm dụng để hoàn thành thuật toán.
Hành vi tiệm cận
Đối với hàm f(n), hành vi tiệm cận là sự tăng trưởng của f(n) khi n lớn. Giá trị đầu vào nhỏ không quan tâm. Nhiệm vụ tìm thời gian cho đầu vào lớn.
Ví dụ: f(n) = c * n + k là tuyến tính. f(n) = c * n² + k là bậc hai.
Phân tích thuật toán chia thành ba trường hợp:
Trường hợp tốt nhất − Tính ranh giới dưới thời gian chạy. Mô tả hành vi thuật toán trong điều kiện tối ưu.
Trường hợp trung bình − Tính vùng giữa ranh giới trên và dưới. Số thao tác không min không max.
Trường hợp xấu nhất − Tính ranh giới trên thời gian chạy. Số thao tác tối đa.
