स्टेप काउंट मेथड एल्गोरिदम का विश्लेषण करने की विधियों में से एक है। इस विधि में, हम गिनते हैं कि एक निर्देश कितनी बार निष्पादित हो रहा है। उससे हम एल्गोरिदम की जटिलता खोजने का प्रयास करेंगे।
मान लीजिए हमारे पास अनुक्रमिक खोज करने के लिए एक एल्गोरिदम है। मान लीजिए प्रत्येक निर्देश को निष्पादित होने में c1, c2, ... समय लगता है, तो हम इस एल्गोरिदम की समय जटिलता खोजने का प्रयास करेंगे।
| एल्गोरिदम | निष्पादन की संख्या | लागत |
|---|---|---|
| seqSearch(arr, n, key) i := 0 while i < n, do if arr[i] = key, then break end if done return i | 1 n+1 n 0/1 1 | c1 c2 c3 c4 c5 |
अब यदि हम निष्पादन की संख्या से गुणा करके लागत जोड़ते हैं (वर्स्ट केस स्थिति मानकर), तो हमें मिलेगा
Cost=c1+(n+1)c 2+nc3+c 4+c 5
Cost=c1+nc 2+c2+nc 3+c 4+c5
Cost=n(c 2+c3)+c 1+c 4+c5
Cost=n(c 2+c3)+C
c1 + c4 + c5 को C मानकर, तो अंतिम समीकरण सीधी रेखा y = mx + b की तरह है। तो हम कह सकते हैं कि फ़ंक्शन रैखिक है। जटिलता O(n) होगी।
