Phương pháp đếm bước là một trong những phương pháp để phân tích thuật toán. Trong phương pháp này, chúng tôi đếm số lần một lệnh được thực thi. Từ đó, chúng tôi sẽ cố gắng tìm ra độ phức tạp của thuật toán.
Giả sử chúng ta có một thuật toán để thực hiện tìm kiếm tuần tự. Giả sử mỗi lệnh sẽ lấy c1, c2,…. khoảng thời gian để thực thi, sau đó chúng tôi sẽ cố gắng tìm ra độ phức tạp về thời gian của thuật toán này
| Thuật toán | Số lần | Chi phí |
|---|---|---|
| seqSearch (arr, n, key) i:=0 trong khi tôi phá vỡ kết thúc nếu xong trả lại tôi | 1 n + 1 N 0/1 1 | c1 c2 c3 c4 c5 |
Bây giờ, nếu chúng ta cộng chi phí bằng cách nhân với số lần nó được thực thi, (xem xét tình huống xấu nhất), chúng ta sẽ nhận được
Chi phí =c1 + (n + 1) c 2 + nc3 + c 4 + c 5
Chi phí =c1 + nc 2 + c2 + nc 3 + c 4 + c5
Chi phí =n (c 2 + c3) + c 1 + c 4 + c5
Chi phí =n (c 2 + c3) + C
Xét c1 + c4 + c5 là C nên phương trình cuối giống như đường thẳng y =mx + b. Vì vậy, chúng ta có thể nói rằng hàm là tuyến tính. Độ phức tạp sẽ là O (n).