Hiệu quả thuật toán

Hiệu quả của thuật toán là thước đo mức độ thực hiện nhiệm vụ nhất định của thuật toán so với việc sử dụng tài nguyên. Một thuật toán hiệu quả thực hiện khối lượng công việc tối đa bằng cách sử dụng ít tài nguyên nhất, chẳng hạn như thời gian, bộ nhớ, bộ nhớ hoặc năng lượng. Hiệu quả của thuật toán có thể được đo lường theo độ phức tạp về thời gian và độ phức tạp về không gian. Trong khoa học máy tính, khái niệm thuật toán hiệu quả thường được so sánh với thuật toán “tốt nhất” hoặc “tối ưu”.

Độ phức tạp về thời gian là thước đo thời gian mà một thuật toán cần để hoàn thành nhiệm vụ của nó so với kích thước của dữ liệu đầu vào. Thuật toán có độ phức tạp về thời gian O(n) có nghĩa là phải mất một khoảng thời gian tuyến tính để hoàn thành, trong đó n là kích thước của đầu vào. Một thuật toán có độ phức tạp về thời gian O(n^2) cần một khoảng thời gian bậc hai để tính toán.

Độ phức tạp của không gian là thước đo lượng bộ nhớ mà thuật toán tiêu thụ. Tiêu chí bộ nhớ cho độ phức tạp của không gian bao gồm độ phức tạp của không gian tổng cộng (tổng bộ nhớ được sử dụng khi kết thúc quá trình chạy thuật toán), độ phức tạp của không gian làm việc (bộ nhớ tối đa được sử dụng tại bất kỳ khoảng thời gian nhất định nào của quá trình chạy thuật toán) và độ phức tạp của không gian phụ trợ (không gian mà thuật toán yêu cầu cho nó). hoạt động sai). Tương tự như độ phức tạp về thời gian, độ phức tạp về không gian cũng được biểu thị bằng ký hiệu Big O.

Các thuật toán hiệu quả nhất là những thuật toán tận dụng tốt nhất không gian và thời gian được phân bổ cho từng nhiệm vụ. Điều này có nghĩa là một thuật toán có độ phức tạp về không gian và thời gian thấp sẽ hoạt động tốt hơn thuật toán có độ phức tạp về không gian và thời gian cao cho một nhiệm vụ nhất định. Hiệu quả của thuật toán là một yếu tố quan trọng trong việc đánh giá chương trình hoặc ứng dụng sẽ hoạt động tốt như thế nào.