Thành viên:AE1525/Nháp 1

Đồ thị của các hàm số thường dùng trong phân tích thuật toán, cho thấy số lượng các phép toán N là kết quả của kích thước đầu vào n cho mỗi hàm

Trong khoa học máy tính lý thuyết, độ phức tạp thời gian là độ phức tạp tính toán mô tả lượng thời gian mà máy tính dùng để chạy một giải thuật. Độ phức tạp thời gian thường được ước lượng bằng cách đếm số phép toán cơ bản được thực hiện bởi giải thuật, giả định rằng việc thực hiện mỗi phép toán cơ bản đó tốn một khoảng thời gian nhất định. Do đó, thời gian chạy và số các phép toán cơ bản của giải thuật được liên kết qua một hằng số.

Bởi vì thời gian thực thi một giải thuật có thể khác nhau ngay cả giữa các đầu vào cùng kích thước, người ta thường xem xét độ phức tạp trong trường hợp tệ nhất, tức là thời gian tối đa cần thiết cho đầu vào với kích thước nhất định. Ít phổ biến hơn, và thường được chỉ rõ một cách tường minh, là độ phức tạp trung bình trường hợp, tức trung bình thời gian cho đầu vào với kích thước nhất định. Trong cả hai trường hợp, độ phức tạp thời gian hay được biểu diễn dưới dạng một hàm số của kích thước đầu vào. Do hàm này nói chung khó để tính toán chính xác, và thời gian chạy đối với các đầu vào nhỏ là không đáng kể, nên người ta thường tập trung vào hành vi tiệm cận của độ phức tạp khi kích thước đầu vào tăng lên. Vì thế, ký hiệu O lớn thường được dùng để thể hiện độ phức tạp thời gian như $O(n)$, $O(n\log n)$, $O(n^{\alpha })$, $O(2^{n})$, v.v., với n đại diện kích thước của đầu vào.

Các độ phức tạp thời gian phổ biến Thành viên:AE1525/Nháp 1

Xem thêm thông tin: Độ phức tạp tính toán của các toán hạng

Thời gian hằng số

Một giải thuật được coi là có độ phức tạp thời gian hằng số (còn được viết là thời gian ${\textstyle O(1)}$) nếu giá trị độ phức tạp giải thuật ${\textstyle T(n)}$ bị giới hạn bởi một giá trị không phụ thuộc vào kích thước đầu vào. Chẳng hạn, truy cập một phần tử bất kỳ trong mảng có độ phức tạp thời gian hằng số vì chỉ có một phép toán được thực thi để tìm vị trí của nó. Tương tự là việc tìm giá trị nhỏ nhất của một mảng đã được sắp xếp tăng dần, bởi vì nó chính là phần tử đầu tiên.

Dù gọi là "thời gian hằng số", thời gian chạy thực tế không nhất thiết phải hoàn toàn độc lập với kích thước bài toán nhưng chặn trên của thời gian chạy phải độc lập với kích thước đó. Như bài toán "hoán đổi giá trị của a và b nếu cần thiết sao cho ${\textstyle a\leq b}$" vẫn được coi có độ phức tạp thời gian hằng số, dù thời gian thực hiện có thể phụ thuộc vào điều kiện ${\textstyle a\leq b}$ đã được thoả mãn hay chưa. Tuy nhiên, luôn tồn tại một hằng số t sao cho thời gian cần thiết không vượt quá t.