Phân tích thuật toán
Phân tích thời gian chạy > Đánh giá độ phức tạp thời gian chạy

Độ phức tạp thời gian chạy cho kịch bản trường hợp xấu nhất của thuật toán đã cho đôi khi có thể được đánh giá bằng cách kiểm tra cấu trúc của thuật toán và đưa ra một số giả định đơn giản hóa. Hãy xem xét các mã giả sau đây:
1    get a positive integer from input
2    if n > 10
3        print "Việc này có thể mất 1 lúc..."
4    for i = 1 to n
5        for j = 1 to i
6            print i * j
7    print "Xong!"
Một máy tính nhất định sẽ mất một lượng thời gian riêng biệt để thực hiện từng hướng dẫn liên quan đến việc thực hiện thuật toán này. Lượng thời gian cụ thể để thực hiện một lệnh đã cho sẽ khác nhau tùy thuộc vào lệnh nào được thực thi và máy tính nào đang thực hiện lệnh đó, nhưng trên máy tính thông thường, lượng này sẽ mang tính quyết định. Giả sử các hành động được thực hiện trong bước 1 được coi là tiêu tốn thời gian T 1, bước 2 sử dụng thời gian T 2, v.v.
Trong thuật toán trên, các bước 1, 2 và 7 sẽ chỉ được chạy một lần. Đối với đánh giá trường hợp xấu nhất, cần giả định rằng bước 3 cũng sẽ được chạy. Do đó, tổng thời gian để chạy các bước 1-3 và bước 7 là:
Các vòng lặp trong các bước 4, 5 và 6 là khó khăn hơn để đánh giá. Kiểm tra vòng lặp bên ngoài trong bước 4 sẽ thực hiện (n + 1) lần (lưu ý rằng cần thêm một bước để chấm dứt vòng lặp for, do đó n + 1 chứ không phải n thực thi), sẽ tiêu tốn thời gian T 4 (n + 1). Mặt khác, vòng lặp bên trong được điều chỉnh bởi giá trị của j, lặp từ 1 đến i. Trong lần đầu tiên đi qua vòng ngoài, j lặp từ 1 đến 1: Vòng lặp bên trong tạo một lượt, do đó, việc chạy thân vòng trong (bước 6) tiêu tốn thời gian T 6 và kiểm tra vòng lặp bên trong (bước 5) tiêu tốn 2 T 5 lần. Trong lần truyền tiếp theo qua vòng ngoài, j lặp từ 1 đến 2: vòng trong tạo ra hai lần, do đó, việc chạy thân vòng trong (bước 6) tiêu tốn 2 T 6 thời gian và kiểm tra vòng trong (bước 5) tiêu tốn 3 T 5 lần.
Nhìn chung, tổng thời gian cần thiết để chạy phần thân vòng trong có thể được biểu diễn dưới dạng một tiến trình số học:
có thể là yếu tố  như
Tổng thời gian cần thiết để chạy thử nghiệm vòng lặp bên ngoài có thể được đánh giá tương tự:
có thể được coi là
Do đó, tổng thời gian chạy cho thuật toán này là:
làm giảm
Theo nguyên tắc thông thường, người ta có thể giả định rằng thành phần bậc cao nhất trong bất kỳ hàm đã cho nào chi phối tốc độ tăng trưởng của nó và do đó xác định thứ tự thời gian chạy của nó. Trong ví dụ này, n 2 là số hạng bậc cao nhất, vì vậy người ta có thể kết luận rằng f (n) = O (n 2). Chính thức điều này có thể được chứng minh như sau:
Prove that  \left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},\ n\geq n_{0}
{\begin{aligned}&\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\\\leq &(n^{2}+n)T_{6}+(n^{2}+3n)T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\ ({\text{for }}n\geq 0)\end{aligned}}



Let k be a constant greater than or equal to [T1..T7]



 {\begin{aligned}&T_{6}(n^{2}+n)+T_{5}(n^{2}+3n)+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq k(n^{2}+n)+k(n^{2}+3n)+kn+5k\\=&2kn^{2}+5kn+5k\leq 2kn^{2}+5kn^{2}+5kn^{2}\ ({\text{for }}n\geq 1)=12kn^{2}\end{aligned}}



Therefore  \left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},n\geq n_{0}{\text{ for }}c=12k,n_{0}=1
Một cách tiếp cận thanh lịch hơn để phân tích thuật toán này sẽ là tuyên bố rằng [ T 1.. T 7 ] đều bằng một đơn vị thời gian, trong một hệ thống các đơn vị được chọn sao cho một đơn vị lớn hơn hoặc bằng thời gian thực tế cho các bước này. Điều này có nghĩa là thời gian chạy của thuật toán bị hỏng như sau:
4+\sum _{i=1}^{n}i\leq 4+\sum _{i=1}^{n}n=4+n^{2}\leq 5n^{2}\ ({\text{for }}n\geq 1)=O(n^{2}).