Trong khoa học máy tính, việc phân tích các thuật toán là xác định độ phức tạp tính toán của các thuật toán, đó là lượng thời gian, lượng lưu trữ và / hoặc các tài nguyên khác cần thiết để thực hiện chúng. Thông thường, điều này liên quan đến việc xác định hàm liên quan đến độ dài của đầu vào thuật toán với số bước cần thực hiện (độ phức tạp thời gian của nó) hoặc số lượng vị trí lưu trữ mà nó sử dụng (độ phức tạp không gian của nó). Một thuật toán được cho là hiệu quả khi các giá trị của hàm này nhỏ hoặc tăng chậm so với tăng của kích thước của đầu vào. Các đầu vào khác nhau có cùng độ dài có thể khiến thuật toán có hành vi khác nhau, do đó, các mô tả trường hợp tốt nhất, xấu nhất và trung bình đều cần được quan tâm trong thực tế. Khi không có yêu cầu khác, hàm mô tả hiệu suất của thuật toán thường là giới hạn trên, được xác định từ các trường hợp xấu nhất với thuật toán.Thuật ngữ "phân tích thuật toán" được đặt ra bởi Donald Knuth.[1] Phân tích thuật toán là một phần quan trọng của lý thuyết phức tạp tính toán rộng hơn, nó cung cấp các ước tính lý thuyết cho các tài nguyên cần thiết cho bất kỳ thuật toán nào giải quyết một vấn đề tính toán nhất định. Các ước tính này cung cấp một cái nhìn sâu sắc về các hướng tìm kiếm hợp lý cho các thuật toán hiệu quả.Trong phân tích lý thuyết của các thuật toán, người ta thường ước tính độ phức tạp của chúng theo nghĩa tiệm cận, nghĩa là ước tính độ phức tạp của hàm với đầu vào lớn tùy ý. Ký hiệu Big O, ký hiệu Big-omega và ký hiệu Big-theta được sử dụng cho mục đích này. Chẳng hạn, tìm kiếm nhị phân được cho là chạy theo một số bước tỷ lệ với logarit của độ dài của danh sách được sắp xếp đang tìm kiếm, hoặc trong O (log (n)), thông thường "trong thời gian logarit ". Thông thường các ước tính tiệm cận được sử dụng vì các triển khai khác nhau của cùng một thuật toán có thể khác nhau về hiệu quả. Tuy nhiên, hiệu quả của bất kỳ hai triển khai "hợp lý" nào của một thuật toán nhất định có liên quan bởi một hằng số nhân được gọi là hằng số ẩn.Các đo đạc độ hiệu quả chính xác (không tiệm cận) đôi khi có thể được tính toán nhưng chúng thường yêu cầu một số giả định nhất định liên quan đến việc thực hiện cụ thể của thuật toán, được gọi là mô hình tính toán. Một mô hình tính toán có thể được định nghĩa theo thuật ngữ của một máy tính trừu tượng, ví dụ: máy Turing và / hoặc bằng cách quy định rằng các hoạt động nhất định được thực hiện trong thời gian đơn vị. Ví dụ: nếu danh sách được sắp xếp mà chúng ta áp dụng tìm kiếm nhị phân có n phần tử và chúng ta có thể đảm bảo rằng mỗi lần tra cứu của một phần tử trong danh sách có thể được thực hiện trong 1 đơn vị thời gian, thì hầu hết cần log2 n + 1 đơn vị thời gian để trả về một kết quả.