วิธีการนับขั้นตอนเป็นวิธีหนึ่งในการวิเคราะห์อัลกอริทึม ในวิธีนี้ เรานับจำนวนครั้งที่ดำเนินการคำสั่งหนึ่งคำสั่ง จากนั้นเราจะพยายามค้นหาความซับซ้อนของอัลกอริทึม
สมมติว่าเรามีอัลกอริธึมเดียวในการค้นหาตามลำดับ สมมติว่าแต่ละคำสั่งจะใช้ c1, c2, …. ระยะเวลาในการดำเนินการ จากนั้นเราจะพยายามค้นหาความซับซ้อนของเวลาของอัลกอริธึมนี้
| อัลกอริทึม | จำนวนครั้ง | ค่าใช้จ่าย |
|---|---|---|
| seqSearch(arr, n, คีย์) ผม :=0 ในขณะที่ฉัน หยุดพัก สิ้นสุด if เสร็จแล้ว ส่งคืนฉัน | 1 n+1 น 0/1 1 | c1 c2 c3 c4 c5 |
ตอนนี้หากเราบวกต้นทุนโดยการคูณจำนวนครั้งที่ดำเนินการ (พิจารณากรณีที่เลวร้ายที่สุด) เราจะได้รับ
ราคา=c1+(n+1)c 2+nc3+c 4+c 5
ราคา=c1+nc 2+c2+nc 3+c 4+c5
ราคา=n(c 2+c3)+c 1+c 4+c5
ราคา=n(c 2+c3)+C
เมื่อพิจารณาว่า c1 + c4 + c5 คือ C ดังนั้นสมการสุดท้ายจึงเหมือนกับเส้นตรง y =mx + b เราก็บอกได้ว่าฟังก์ชันเป็นเส้นตรง ความซับซ้อนจะเป็น O(n)
