ধাপ গণনা পদ্ধতি অ্যালগরিদম বিশ্লেষণ করার পদ্ধতিগুলির মধ্যে একটি। এই পদ্ধতিতে, আমরা একটি নির্দেশ কার্যকর করার সংখ্যা গণনা করি। সেখান থেকে আমরা অ্যালগরিদমের জটিলতা খুঁজে বের করার চেষ্টা করব।
অনুক্রমিক অনুসন্ধান করার জন্য আমাদের একটি অ্যালগরিদম আছে। ধরুন প্রতিটি নির্দেশে c1, c2, …. কার্যকর করার জন্য কতটা সময়, তারপর আমরা এই অ্যালগরিদমের সময়ের জটিলতা খুঁজে বের করার চেষ্টা করব
| অ্যালগরিদম | বার সংখ্যা | খরচ |
|---|---|---|
| seqSearch(arr, n, key) i :=0 যখন আমি বিরতি যদি শেষ সম্পন্ন প্রত্যাবর্তন i | 1 n+1 n 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)।
