Một phép đo thường được sử dụng được sử dụng để xác định độ phức tạp của một vấn đề tính toán là gì?
Để đo lường sự khó khăn của việc giải quyết một vấn đề tính toán, người ta có thể muốn xem bao nhiêu thời gian thuật toán tốt nhất đòi hỏi để giải quyết vấn đề. Tuy nhiên, thời gian chạy có thể, nói chung, phụ thuộc vào các trường hợp. Đặc biệt, trường hợp lớn hơn sẽ đòi hỏi nhiều thời gian hơn để giải quyết. Do đó, thời gian cần thiết để giải quyết một vấn đề (hoặc không gian cần thiết, hoặc bất kỳ biện pháp phức tạp) được tính toán như là một chức năng của kích thước của các trường hợp. Điều này thường được thực hiện để có kích thước của đầu vào trong bit. Lý thuyết phức tạp quan tâm đến cách thuật toán quy mô với sự gia tăng kích thước đầu vào. Ví dụ, trong vấn đề tìm kiếm cho dù một đồ thị được kết nối, bao nhiêu thời gian nữa để giải quyết một vấn đề cho một đồ thị với 2n đỉnh so với thời gian thực hiện cho một đồ thị với n đỉnh?
Thuật toán tốt nhất cần bao nhiêu thời gian để giải quyết vấn đề?