Phân tích tiệm cận
Sử dụng phân tích tiệm cận, ta có thể hình dung về hiệu năng của thuật toán dựa trên kích thước đầu vào. Không nên tính thời gian chạy chính xác, mà nên 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 là tìm mối quan hệ hoặc hàm chỉ ra bao nhiêu không gian trong bộ nhớ chính được chiếm dụng để hoàn thành thuật toán.
Hành vi tiệm cận (Asymptotic Behavior)
Đố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. Các giá trị đầu vào nhỏ không được quan tâm. Nhiệm vụ là tìm thời gian cần thiết cho giá trị đầu vào lớn.
Ví dụ: f(n) = c * n + k là độ phức tạp thời gian tuyến tính. f(n) = c *(n*n) + k là độ phức tạp thời gian bậc hai.
Phân tích thuật toán có thể chia thành ba trường hợp khác nhau như sau:
Trường hợp tốt nhất (Best Case) − Tính ranh giới dưới của 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 (Average Case) − Tính vùng giữa ranh giới trên và dưới của thời gian chạy. Số thao tác thực thi không tối thiểu cũng không tối đa.
Trường hợp xấu nhất (Worst Case) − Tính ranh giới trên của thời gian chạy. Số thao tác thực thi tối đa.
