परिशोधन विश्लेषण संचालन के अनुक्रम के लिए रन टाइम, अनुक्रम द्वारा आवश्यक औसत समय निर्धारित करने के लिए उपयोग किया जाता है। एल्गोरिदम पर किए गए औसत-केस विश्लेषण के रूप में नहीं माना जा सकता क्योंकि यह हमेशा औसत केस परिदृश्य नहीं लेता है। ऐसे मामले हैं जो विश्लेषण के सबसे खराब स्थिति के रूप में होते हैं। इसलिए, परिशोधन विश्लेषण को एक क्रम में कई ऑपरेशनों के लिए सबसे खराब स्थिति वाला विश्लेषण माना जा सकता है। यहां, प्रत्येक ऑपरेशन को अलग-अलग करने की लागत और कुछ के लिए इसकी उच्च। बाइनरी काउंटर का उपयोग करते हुए यह समस्या एक सामान्य दृश्य है।
आइए देखें कि सी ++ प्रोग्रामिंग भाषा में काम करना और कार्यान्वयन करना ताकि हम अवधारणाओं के साथ स्पष्ट हो सकें।
एक k-बिट बाइनरी काउंटर को लंबाई k के बाइनरी ऐरे का उपयोग करके कार्यान्वित किया जाता है, जिसका प्रारंभ में मान 0 होता है। इस मान पर, इंक्रीमेंट ऑपरेशन कई बार किया जाता है। यहां बताया गया है कि बाइनरी 8-बिट सरणी उस पर किए गए इंक्रीमेंट ऑपरेशन पर कैसे व्यवहार करेगी।
प्रारंभ में, 00000000> 00000001> 00000010> 00000011> 00000100> 00000101>....> 11111111.
यह तर्क संख्या के अंतिम बिट से पहले 0 की घटना की जाँच करने के लिए है और इसे 1 पर फ़्लिप करना है और सभी बिट्स क्रमिक रूप से 0 पर इसका अनुसरण करते हैं।
उदाहरण
#include <iostream>
using namespace std;
int main(){
int number[] = {1,0,0,1,0,1,1,1};
int length = 8;
int i = length - 1;
while (number[i] == 1) {
number[i] = 0;
i--;
}
if (i >= 0)
str[i] = 1;
for(int i = 0 ; i<length ; i++)
cout<<number[i]<<" ";
} आउटपुट
1 0 0 1 0 0 0 0
इस समस्या में, प्रत्येक ऑपरेशन की लागत स्थिर होती है और बिट्स की संख्या पर निर्भर नहीं करती है,
यहाँ एक अनुक्रम की लागत के लिए स्पर्शोन्मुख विश्लेषण O(n) है।
n संचालन में किए जाने वाले फ़्लिप की कुल संख्या है - n + n/2 + n/4 +….. + n/k 2 k फ़्लिप की संख्या में।
यह हर में HP वाला GP है।
फ्लिप का योग
योग =n + n/2 + n/4 + ….. + n/k
2
अब, संचालन की सुगंधित लागत O(n) / 2n =O(1) . है
क्रम O(1) है जो संख्या में बिट्स की संख्या n के समानुपाती नहीं है।